Submission #524229

#	Time	Username	Problem	Language	Result	Execution time	Memory
524229		CPSC	Weighting stones (IZhO11_stones)	C++14	100 / 100	198 ms	4700 KiB

stones

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
struct nod {
    int mn;
    int mx;
};
nod tree[4*N],emp;
int lazy[4*N],n,a[N];
nod merge(nod a, nod b) {
    nod x;
    x.mn = min(a.mn,b.mn);
    x.mx = max(a.mx,b.mx);
    return x;
}
void update(int node,int le,int ri,int start,int end,int val) {
	if(lazy[node]) {
		tree[node].mn += lazy[node];
		tree[node].mx += lazy[node];
		if(le != ri) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node]=0;
	}
	if(le > end || ri < start) 
	return ;
	if(start <= le && ri <= end) {
		tree[node].mn += val;
		tree[node].mx += val;
		if(le != ri) {
			lazy[2*node] += val;
			lazy[2*node+1] += val;
		}
		return;
	}
	int mid = (le + ri) / 2;
	update(2*node,le,mid,start,end,val);
	update(2*node+1,mid+1,ri,start,end,val);
	tree[node] = merge(tree[2*node], tree[2*node+1]);
}
nod getans(int node,int le,int ri,int start,int end) {
	if(lazy[node]) {
		tree[node].mn += lazy[node];
		tree[node].mx += lazy[node];
		if(le != ri) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node]=0;
	}
	if(le > end || ri < start) return emp;
	if(start <= le && ri <= end) {
		return tree[node];
	}
	int mid = (le + ri) / 2;
	return merge(getans(2*node,le,mid,start,end), getans(2*node+1,mid+1,ri,start,end));
}
main() {
    emp.mx = -1e9;
    emp.mn = 1e9;
    cin>>n;
    int mx,mxty,ty;
    mx = 0;
    for (int i = 1; i <= n; i++) {
        cin>>a[i]>>ty;
        if (ty == 1)
        update(1,1,n,1,a[i],1); else update(1,1,n,1,a[i],-1);
        if (a[i] > mx) {
            mxty = ty;
            mx = a[i];
        } 
        if (mxty == 1) {
            //if (i == 3) cout<<getans(1,1,n,1,n).mn<<endl;
            if (getans(1,1,n,1,n).mn < 0) cout<<"?"<<endl;
            else cout<<">"<<endl;
            continue;
        } 
        if (mxty == 2) {
            if (getans(1,1,n,1,n).mx > 0) cout<<"?"<<endl;
            else cout<<"<"<<endl;
        }
    }
}

Compilation message (stderr)

stones.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main() {
      | ^~~~
stones.cpp: In function 'int main()':
stones.cpp:82:9: warning: 'mxty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |         if (mxty == 2) {
      |         ^~

• Subtask 1: 100 / 100