Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 13:17:26
2018-05-26 13:15:31
Task:Coins
Sender:Wave of Technology
Submission time:2018-05-26 13:17:26
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.89 / 1.00details
#2ACCEPTED0.57 / 1.00details
#3ACCEPTED0.63 / 1.00details
#4ACCEPTED0.65 / 1.00details
#5ACCEPTED0.79 / 1.00details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:142:8: warning: 'toleft' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll toleft;
        ^~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1000000000000000LL;

struct STLP {
  vector<ll> t;
  int SZ;
  vector<ll> pending;
  vector<bool> ispending;

  STLP (int N) {
    SZ = 1;
    while (SZ<N) { SZ *= 2; }
    t= vector<ll> (2*SZ, 0);
    pending= vector<ll> (2*SZ, 0);
    ispending= vector<bool> (2*SZ, 0);
  }

  int rangesize (int i) const {
    int c=1;
    while ( i<SZ ) {
      c = 2*c;
      i *= 2;
    }
    return c;
  }

  void propagate_subtree(int i) {
    if (!ispending[i]) { return; }

    if (i<SZ) {
      set_to_subtree(2*i, pending[i]);
      set_to_subtree(2*i+1, pending[i]);
      
    }

    ispending[i] = false;
    pending[i] = 0;
  }

  void set_to_subtree(int i, ll val) {
    if (!ispending[i]) {
      pending[i] = val;

    } else {
      pending[i] += val;
    }

    t[i] += val;
    
    ispending[i] = true;
  }

  void fix_to_root(int i) {
    i/=2;
    while (i>0) {
      t[i] = max(t[2*i], t[2*i+1]);
      i /= 2;
    }
  }

  void propagate_from_root(int i) {
    for (int k=30; k>=0; k--) {
      if (i>>k)
	propagate_subtree(i>>k);
    }
  }

  void set_range(int a, int b, ll val) {
    a += SZ;
    b += SZ;
    propagate_from_root(a);
    propagate_from_root(b);

    int left = 0;
    int right = 0;
    while (b>=a) {
      if (a%2) {
	set_to_subtree(a, val);
	if (!left) left = a;
	a++;
      }
      if (!(b%2)) {
	set_to_subtree(b, val);
	if (!right) right = b;
	b--;
      }
      a /= 2;
      b /= 2;
    }
    fix_to_root(left);
    fix_to_root(right);
  }

  ll get_range(int a, int b) {
    ll res = -INF;
    a += SZ;
    b += SZ;
    propagate_from_root(a);
    propagate_from_root(b);
    while (b>=a) {
      if (a%2) {
	res = max(res, t[a]);
	a++;
      }
      if (!(b%2)) {
	res = max(res, t[b]);
	b--;
      }
      a /= 2;
      b /= 2;
    }
    return res;
  }
  
};


int main() {

  cin.tie(NULL);
  std::ios::sync_with_stdio(false);

  ll n;
  cin >> n;

  //  STLP test(100);
  //  test.set_range(0, 10, 10);
  //  cout << "test: " << test.get_range(0, 10) << endl;
  
  STLP left(n+100);
  STLP right(n+100);

  for (int i=0; i<n; i++) {
    ll c, st;
    cin >> c >> st;

    ll toleft;
    if (st == 1) { toleft = 1; }
    if (st == 2) { toleft = -1; }

    left.set_range(0, c, toleft);
    right.set_range(0, c, -toleft);

    ll maxl = left.get_range(0, n+10);
    ll maxr = right.get_range(0, n+10);

    //    cout << "TO: " << c << " " << toleft << endl;
    //    cout << "MAX: " << maxl << " " << maxr << endl;
    
    if (maxl <= 0) {
      cout << '<' << endl;
    } else if (maxr <= 0) {
      cout << '>' << endl;
    } else {
      cout << '?' << endl;
    }
  }
  
}

Test details

Test 1

Verdict: ACCEPTED

input
200000
175878 1
146174 1
4939 2
181388 1
27963 2
28393 1
101955 2
129380 1
53446 1
56883 2
41641 2
52574 1
185690 2
17672 2
187 2
29223 1
116434 2
81263 2
153912 2
...
view   save

correct output
>
>
>
>
>
>
>
>
>
>
>
>
?
?
?
?
?
?
?
?
...
view   save

user output
>
>
>
>
>
>
>
>
>
>
>
>
?
?
?
?
?
?
?
?
...
view   save

Test 2

Verdict: ACCEPTED

input
200000
1 2
2 1
3 2
4 1
5 2
6 1
7 2
8 1
9 2
10 1
11 2
12 1
13 2
14 1
15 2
16 1
17 2
18 1
19 2
...
view   save

correct output
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
...
view   save

user output
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
...
view   save

Test 3

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
5 1
6 2
7 2
8 2
9 2
10 2
11 1
12 1
13 1
14 1
15 1
16 2
17 2
18 2
19 2
...
view   save

correct output
>
>
>
>
>
?
?
?
?
<
?
?
?
?
>
?
?
?
?
<
...
view   save

user output
>
>
>
>
>
?
?
?
?
<
?
?
?
?
>
?
?
?
?
<
...
view   save

Test 4

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
...
view   save

correct output
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
...
view   save

user output
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
...
view   save

Test 5

Verdict: ACCEPTED

input
200000
188909 2
58944 1
26824 1
143263 2
108129 2
170746 1
129857 2
151652 1
92616 1
5122 1
85017 2
133713 2
130510 1
23167 2
55879 2
81852 1
117028 1
185678 1
5335 2
...
view   save

correct output
<
<
?
<
<
<
<
?
?
?
?
?
?
?
?
?
?
?
?
?
...
view   save

user output
<
<
?
<
<
<
<
?
?
?
?
?
?
?
?
?
?
?
?
?
...
view   save