# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
344372 | nicolaalexandra | 돌 무게 재기 (IZhO11_stones) | C++14 | 324 ms | 4648 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
struct segment_tree{
int mini,maxi,lazy;
} aint[DIM*4];
int n,x,nr,i;
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].mini += aint[nod].lazy;
aint[fiu_st].maxi += aint[nod].lazy;
aint[fiu_st].lazy += aint[nod].lazy;
aint[fiu_dr].mini += aint[nod].lazy;
aint[fiu_dr].maxi += aint[nod].lazy;
aint[fiu_dr].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].maxi += val;
aint[nod].mini += val;
aint[nod].lazy += val;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
aint[nod].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
aint[nod].maxi = max (aint[nod<<1].maxi,aint[(nod<<1)|1].maxi);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++){
cin>>x>>nr;
if (nr == 1)
update (1,1,n,1,x,1);
else update (1,1,n,1,x,-1);
if (aint[1].mini >= 0)
cout<<">\n";
else {
if (aint[1].maxi <= 0)
cout<<"<\n";
else cout<<"?\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |