oj.uz

Submission #171054

# Submission time Handle Problem Language Result Execution time Memory
171054 2019-12-27T08:47:21 Z mosiashvililuka Simple game (IZhO17_game) C++14
0 / 100
 5 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,f[100009],tp,fen[200009],kk,zx,xc;
pair <int, int> p[100009];
map <int, int> m;
map <int, int>::iterator it;
void upd(int q, int w){
	while(q<=kk){
		fen[q]+=w;
		q=q+(q&(-q));
	}
}
int read(int q){
	int jm=0;
	while(q>=1){
		jm+=fen[q];
		q=q-(q&(-q));
	}
	return jm;
}
void mak(int q){
	if(q<1) return;
	if(f[q]<=f[q+1]){
		upd(f[q],-1);
		upd(f[q+1],1);
	}else{
		upd(f[q+1]+1,-1);
		upd(f[q]+1,1);
	}
}
void makt(int q){
	if(q<1) return;
	if(f[q]<=f[q+1]){
		upd(f[q],1);
		upd(f[q+1],-1);
	}else{
		upd(f[q+1]+1,1);
		upd(f[q]+1,-1);
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	//scanf("%d%d\n",&a,&b);
	for(i=1; i<=a; i++){
		cin>>f[i];
		//scanf("%d",&f[i]);
		m[f[i]]=1;
	}
	f[a+1]=f[a]+1;
	m[f[a+1]]=1;
	for(i=1; i<=b; i++){
		//scanf("%d",&tp);
		cin>>tp;
		if(tp==2){
			//scanf("%d\n",&c);
			cin>>c;
			p[i].first=c;
			m[p[i].first]=1;
		}else{
			//scanf("%d%d\n",&c,&d);
			cin>>c>>d;
			p[i].first=c;p[i].second=d;
			m[p[i].second]=1;
		}
	}
	c=0;
	for(it=m.begin(); it!=m.end(); it++){
		c++;
		m[(*it).first]=c;
	}
	for(i=1; i<=a; i++) f[i]=m[f[i]];
	for(i=1; i<=b; i++){
		if(p[i].second!=0) p[i].second=m[p[i].second]; else p[i].first=m[p[i].first];
	}
	f[a+1]=m[f[a+1]];
/*	for(i=1; i<=a+1; i++) cout<<f[i]<<" ";
	cout<<endl;
	for(i=1; i<=b; i++){
		cout<<p[i].first<<" "<<p[i].second<<endl;
	}*/
	kk=a+b+2;
	for(i=1; i<=a; i++){
		if(f[i]<=f[i+1]){
			upd(f[i],1);
			upd(f[i+1],-1);
		}else{
			upd(f[i+1]+1,1);
			upd(f[i]+1,-1);
		}
	}
	for(i=1; i<=a; i++){
		if(p[i].second==0){
			cout<<read(p[i].first)<<endl;
		}else{
			mak(p[i].first);
			mak(p[i].first-1);
			f[p[i].first]=p[i].second;
			makt(p[i].first);
			makt(p[i].first-1);
		}
	}
	return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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