Submission #87049

#	Time	Username	Problem	Language	Result	Execution time	Memory
87049		rakuten	Weighting stones (IZhO11_stones)	C++14	0 / 100	66 ms	2628 KiB

stones

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)1e5 + 7;

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		while (pos < N) {
			tree[pos] += val;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};
fen tr[3];
int n ;
int a[N];
int R[N], S[N] , r , s;

int get() {
	int l = 0;
	int r = n + 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (tr[1].get(mid, n) + tr[2].get(mid, n) == 0) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return a[l];
}
int  x1 , x2;
set < int > v ;
set < int > :: iterator  vi ;
set < int > q ;
set < int > :: iterator  qi ;
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	if (n <= 10000 )
    {
      for (int i = 0 ;i < n ;i ++ )
     {
         x1 = 0 ;
         x2 = 0 ;
         cin >> r >> s ;
         if (i == 0)
         {
            if (s == 1)
                cout << '>' << endl ;
            else
                cout << '<' << endl ;
            if (s == 1)
                v.insert (r) ;
            else
                q.insert (r) ;
         }
         else
         {

            if (s == 1)
                v.insert (r) ;
            else
                q.insert (r) ;
            if (v.size() == 0)
                cout << '<' << endl ;
            else
            if (q.size() == 0 )
                cout << '>' << endl ;
            else
            {
                qi = -- q.end();

                for (vi = --v.end(); ; vi -- )
                {
                    if ( (*vi) > (*qi))
                        x1 ++ ;
                    else
                        x2 ++ ;
                    if (qi == q.begin()|| vi == v.begin()  || (x1 > 0 && x2 > 0) )
                        break;
                    qi -- ;
                }
                if (x1 > x2 && x2 == 0 && x1 == q.size())
                    cout << '>' << endl ;
                else
                if (x1 < x2 && x1 == 0 && x2 == v.size())
                    cout << '<' << endl;
                else
                    cout << '?' << endl ;
            }
        }
     }
     exit(0) ;
    }
	ll sum1, sum2;
	sum1 = sum2 = 0;
	int last = -1;
	for (int i = 1; i <= n; i++) {
		int r, s;
		cin >> r >> s;
		a[r] = s;
		R[i] = r;
		S[i] = s;
		if (s == 1) {
			sum1 += (n - r);
		} else {
			sum2 += (n - r);
		}
		tr[s].upd(r, 1);
	}
	vector < char > ans;
	for (int i = n; i >= 1; i--) {
		int last = get();
		int res1, res2;
		res1 = tr[1].get(1, n);
		res2 = tr[2].get(1, n);
		if (last == 1) {
			if (res1 == res2) {
				if (sum1 >= sum2) {
					ans.push_back('?');
				} else {
					ans.push_back('>');
				}
			} else if (res1 > res2) {
				ans.push_back('>');
			} else {
				ans.push_back('?');
			}
		} else {
			if (res1 == res2) {
				if (sum1 <= sum2) {
					ans.push_back('?');
				} else {
					ans.push_back('<');
				}
			} else if (res1 < res2) {
				ans.push_back('<');
			} else {
				ans.push_back('?');
			}
		}
		tr[S[i]].upd(R[i], -1);
		if (S[i] == 1) {
			sum1 -= (n - R[i]);
		} else {
			sum2 -= (n - R[i]);
		}
	}
	reverse(ans.begin(), ans.end());
	for (char to : ans) {
		cout << to << '\n';
	}
}

Compilation message (stderr)

stones.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
stones.cpp: In function 'int main()':
stones.cpp:104:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (x1 > x2 && x2 == 0 && x1 == q.size())
                                           ~~~^~~~~~~~~~~
stones.cpp:107:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (x1 < x2 && x1 == 0 && x2 == v.size())
                                           ~~~^~~~~~~~~~~
stones.cpp:118:6: warning: unused variable 'last' [-Wunused-variable]
  int last = -1;
      ^~~~

• Subtask 1: 0 / 100