CSES - HIIT Open 2018 - Results
Submission details
Task:Coins
Sender:Wave of Technology
Submission time:2018-05-26 13:17:26 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.89 sdetails
#2ACCEPTED0.57 sdetails
#3ACCEPTED0.63 sdetails
#4ACCEPTED0.65 sdetails
#5ACCEPTED0.79 sdetails

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
...

correct output
>
>
>
>
>
...

user output
>
>
>
>
>
...

Test 2

Verdict: ACCEPTED

input
200000
1 2
2 1
3 2
4 1
...

correct output
<
>
<
>
<
...

user output
<
>
<
>
<
...

Test 3

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
...

correct output
>
>
>
>
>
...

user output
>
>
>
>
>
...

Test 4

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
...

correct output
>
>
>
>
>
...

user output
>
>
>
>
>
...

Test 5

Verdict: ACCEPTED

input
200000
188909 2
58944 1
26824 1
143263 2
...

correct output
<
<
?
<
<
...

user output
<
<
?
<
<
...