oj.uz

Submission #960900

# Submission time Handle Problem Language Result Execution time Memory
960900 2024-04-11T07:57:41 Z pcc Synchronization (JOI13_synchronization) C++17
30 / 100
 337 ms 19944 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
set<int> ls,rs;
int N,M,Q;
int op[mxn*2];
bitset<mxn> done;

struct SEG{
#define mid ((l+r)>>1)
	pii seg[mxn*4];
	SEG(){
		for(auto &i:seg)i.fs = i.sc = -1e9;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc = max(seg[now].sc,v);
			return;
		}
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
		seg[now].fs = max({seg[now*2+1].fs,seg[now*2+1].sc,seg[now*2+2].fs,seg[now*2+2].sc});
		return;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return max(seg[now].fs,seg[now].sc);
		if(mid>=e)return max(seg[now].sc,getval(now*2+1,l,mid,s,e));
		else if(mid<s)return max(seg[now].sc,getval(now*2+2,mid+1,r,s,e));
		else return max({seg[now].sc,getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e)});
	}
#undef mid
};

SEG lseg,rseg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	for(int i = 1;i<N;i++){
		int a;
		cin>>a>>a;
	}
	for(int i = 1;i<=M;i++)cin>>op[i];
	for(int i = 1;i<=N;i++){
		ls.insert(i);
		rs.insert(i);
		lseg.modify(0,1,N,i,i,-i);
		rseg.modify(0,1,N,i,i,i);
	}
	for(int i = 1;i<=M;i++){
		int id = op[i];
		if(done[id]){
			done[id] = false;
			ls.insert(id);
			rs.insert(id+1);
			continue;
		}
		done[id] = true;
		ls.erase(id);
		rs.erase(id+1);
		auto lp = *(--rs.upper_bound(id));
		auto rp = *(ls.lower_bound(id+1));
		lseg.modify(0,1,N,lp,rp,lseg.getval(0,1,N,lp,rp));
		rseg.modify(0,1,N,lp,rp,rseg.getval(0,1,N,lp,rp));
	}
	while(Q--){
		int k;
		cin>>k;
		cout<<rseg.getval(0,1,N,k,k)+lseg.getval(0,1,N,k,k)+1<<'\n';
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Incorrect 2 ms 6744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 24 ms 7744 KB Output is correct
8 Correct 321 ms 19944 KB Output is correct
9 Correct 312 ms 19796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 16912 KB Output is correct
2 Correct 196 ms 19104 KB Output is correct
3 Correct 211 ms 19212 KB Output is correct
4 Correct 198 ms 19248 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -