oj.uz

Submission #283770

# Submission time Handle Problem Language Result Execution time Memory
283770 2020-08-26T07:06:47 Z AMO5 Tenis (COI19_tenis) C++17
30 / 100
 500 ms 22488 KB 
//koosaga's sol
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=1e5+5;
bool DEBUG=0;

int n,q;
int a[3][mxn];
map<int,int>pos[3];

ll tree[mxn*4],lazy[mxn*4];

void puttag(int id, int v){
	tree[id]+=v;
	lazy[id]+=v;
	return;
}

void pushdown(int id, int le, int ri){
	ll x = lazy[id];
	lazy[id]=0ll;
	if(le==ri||x==0)return;
	puttag(id*2,x);
	puttag(id*2+1,x);
	return;
}

void pushup(int id, int le, int ri){
	tree[id]=min(tree[id*2],tree[id*2+1]);
	return;
}

void upd(int x, int y, int v, int id=1, int le=0, int ri=n-2){
	if(x>ri||le>y)return;
	if(x<=le&&ri<=y){
		puttag(id,v);
		return;
	}
	pushdown(id,le,ri);
	int mid=(le+ri)/2;
	upd(x,y,v,id*2,le,mid);
	upd(x,y,v,id*2+1,mid+1,ri);
	pushup(id,le,ri);
}

int query(int x, int y, int id=1, int le=0, int ri=n-2){
	if(x>ri||le>y)return 1e9;
	if(x<=le&&ri<=y){
		//cerr<<id<<" "<<le<<" "<<ri<<" : "<<tree[id]<<"\n";
		return tree[id];
	}
	pushdown(id,le,ri);
	int mid=(le+ri)/2;
	int left = query(x,y,id*2,le,mid);
	int right = query(x,y,id*2+1,mid+1,ri);
	return min(left,right);
}

void add(int x, int v){
	int mn = min({pos[0][x],pos[1][x],pos[2][x]});
	int mx = max({pos[0][x],pos[1][x],pos[2][x]});
	//cerr<<x<<": "<<mn<<" "<<mx-1<<" "<<v<<"\n";
	upd(mn,mx-1,v);
}

void run(int id=1, int le=0, int ri=n-2){
	cerr<<id<<" "<<le<<" "<<ri<<" "<<tree[id]<<" \n";
	if(le==ri)return;
	int mid=(le+ri)>>1;
	run(id*2,le,mid);
	run(id*2+1,mid+1,ri);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>n>>q;
    for(int i=0; i<3; i++){
		for(int j=0; j<n; j++){
			cin>>a[i][j];
			a[i][j]--;
			pos[i][a[i][j]]=j;
		}
	}
	for(int i=0; i<n; i++){
		add(i,+1);
	}
	//run();
	while(q--){
		int typ;
		cin>>typ;
		if(typ==1){
			int x; cin>>x;
			x--;
			int mn = min({pos[0][x],pos[1][x],pos[2][x]});
			//cerr<<"checking 0 "<<mn-1<<"\n";
			cout<<(query(0,mn-1)?"DA":"NE")<<"\n";
		}else{
			int p,x,y;
			cin>>p>>x>>y;
			p--; x--; y--;
			add(x,-1); add(y,-1);
			int posx = pos[p][x];
			int posy = pos[p][y];
			swap(pos[p][x],pos[p][y]);
			add(x,+1); add(y,+1);
		}
		//run();
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:122:8: warning: unused variable 'posx' [-Wunused-variable]
  122 |    int posx = pos[p][x];
      |        ^~~~
tenis.cpp:123:8: warning: unused variable 'posy' [-Wunused-variable]
  123 |    int posy = pos[p][y];
      |        ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 298 ms 21368 KB Output is correct
14 Correct 326 ms 21496 KB Output is correct
15 Correct 396 ms 21368 KB Output is correct
16 Correct 413 ms 21356 KB Output is correct
17 Correct 356 ms 21368 KB Output is correct
18 Correct 318 ms 21508 KB Output is correct
19 Correct 308 ms 21240 KB Output is correct
20 Correct 319 ms 21496 KB Output is correct
21 Correct 289 ms 21372 KB Output is correct
22 Correct 304 ms 21504 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 680 ms 22488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 298 ms 21368 KB Output is correct
14 Correct 326 ms 21496 KB Output is correct
15 Correct 396 ms 21368 KB Output is correct
16 Correct 413 ms 21356 KB Output is correct
17 Correct 356 ms 21368 KB Output is correct
18 Correct 318 ms 21508 KB Output is correct
19 Correct 308 ms 21240 KB Output is correct
20 Correct 319 ms 21496 KB Output is correct
21 Correct 289 ms 21372 KB Output is correct
22 Correct 304 ms 21504 KB Output is correct
23 Execution timed out 680 ms 22488 KB Time limit exceeded
24 Halted 0 ms 0 KB -