# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48428 | ernestvw | Weighting stones (IZhO11_stones) | C++11 | 206 ms | 13996 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int maxn = 1<<17;
class SegmentTree {
public:
int n;
vi sum,minsuffix,maxsuffix;
SegmentTree(int _n) : n(_n), sum(2*_n,0),
minsuffix(2*_n,0), maxsuffix(2*_n,0) {}
void update(int i,int v) {
i+=n;
maxsuffix[i]=minsuffix[i]=sum[i]=v;
while((i/=2)>0) {
sum[i]=sum[2*i]+sum[2*i+1];
minsuffix[i]=min(minsuffix[2*i]+sum[2*i+1],minsuffix[2*i+1]);
maxsuffix[i]=max(maxsuffix[2*i]+sum[2*i+1],maxsuffix[2*i+1]);
}
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin>>N;
SegmentTree segTree(maxn);
for(int i=1;i<=N;i++) {
int w;
int s;
cin>>w>>s;
segTree.update(w-1, s==1 ? 1 : -1);
bool rHeavier = segTree.minsuffix[1]<0;
bool lHeavier = segTree.maxsuffix[1]>0;
if(rHeavier && lHeavier) cout<<'?'<<endl;
else if(rHeavier) cout<<'<'<<endl;
else if(lHeavier) cout<<'>'<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |