Submission #124351

#	Time	Username	Problem	Language	Result	Execution time	Memory
124351		Adhyyan1252	Tenis (COI19_tenis)	C++11	100 / 100	482 ms	13380 KiB

tenis

#include<bits/stdc++.h>

using namespace std;

//let ai hold the size of union of prefix
//find minimum ai - i
//update the prefix 

#define INF 1e7
struct segtree{
	vector<int> t,l;
	int sz;
	
	segtree(int size){
		sz = size;
		t = vector<int>(sz*4, 0);
		l = vector<int>(sz*4, 0);
	}
	
	void prop(int i, int s, int e){
		if(l[i] == 0) return;
		t[i] += l[i];
		if(s != e){
			l[i*2] += l[i];
			l[i*2+1] += l[i];
		}
		l[i] = 0;
	}
	
	int query(int i, int s, int e, int l, int r){
		prop(i, s, e);
		if(s > r || e < l || s > e) return INF;
		if(l <= s && e <= r) return t[i];
		int m = (s + e)/2;
		return min(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
	}
	
	void upd(int i, int s, int e, int L, int r, int val){
		prop(i, s, e);
		if(L <= s && e <= r){
			l[i] = val;
			prop(i, s, e);
			return;
		}
		if(s > r || e < L) return;
		int m = (s + e)/2;
		upd(i*2, s, m, L, r, val);
		upd(i*2+1, m+1, e, L, r, val);
		t[i] = min(t[i*2], t[i*2+1]);
	}
	
	
};


int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<vector<int> > perm(3, vector<int>(n));
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < n; j++){
			cin>>perm[i][j];
			perm[i][j]--;
		}
	}
	
	vector<vector<int> > a(n, vector<int>(3));
	for(int j = 0; j < 3; j++){
		for(int i = 0; i < n; i++){
			a[perm[j][i]][j] = i;
		}
	}
	
	segtree s(n);
	
	for(int i = 0; i < n; i++){
		s.upd(1, 0, s.sz-1, i, i, -(i+1));
	}
	for(int i = 0; i < n; i++){
		int low = INF;
		for(int j = 0; j < 3; j++) low = min(low, a[i][j]);
		s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
	}
	
	for(int qt = 0; qt < q; qt++){
		int type; cin>>type; 
		if(type == 1){
			int indx; cin>>indx; indx--;
			int low = INF;
			for(int j = 0; j < 3; j++) low = min(low, a[indx][j]);
			int ret = s.query(1, 0, s.sz-1, 0, low-1);
			//cout<<"Q "<<indx<<" "<<low<<" "<<ret<<endl;
			assert(ret >= 0);
			if(ret == 0){
				cout<<"NE"<<endl;
			}else{
				cout<<"DA"<<endl;
			}
		}else{
			int p, x, y; cin>>p>>x>>y; p--, x--, y--;
			
			//first remove from segtree
			
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[x][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, -1);
			}
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[y][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, -1);
			}
			
			swap(a[x][p], a[y][p]);
			
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[x][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
			}
			{
				int low = INF;
				for(int j = 0; j < 3; j++) low = min(low, a[y][j]);
				s.upd(1, 0, s.sz-1, low, s.sz-1, 1);
			}	
		}
	}
	
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49