Submission #201116

#	Time	Username	Problem	Language	Result	Execution time	Memory
201116		grt	Tenis (COI19_tenis)	C++17	100 / 100	180 ms	7928 KiB

tenis

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Node {
	int f,g;
};

const int nax = 100*1000+10;
int n,q;
int t[3][nax],ord[3][nax];
Node T[(1<<18)];

int last(int a) {
	return max({ord[0][a],ord[1][a],ord[2][a]});
}

void propagate(int a) {
	T[2*a].g+=T[a].g;
	T[2*a+1].g+=T[a].g;
	T[a].g=0;
}

void init(int l,int r,int v) {
	if(l==r) {
		T[v].f = l;
		return;
	}
	int mid = (l+r)/2;
	init(l,mid,v*2);
	init(mid+1,r,v*2+1);
	T[v].f = min(T[v*2].f,T[v*2+1].f);
}

void update(int a,int b,int l,int r,int v,int val) {
	if(a<=l&&r<=b) {
		T[v].g+=val;
		return;
	}
	propagate(v);
	int mid = (l+r)/2;
	if(a<=mid) update(a,b,l,mid,v*2,val);
	if(mid<b) update(a,b,mid+1,r,v*2+1,val);
	T[v].f = min(T[2*v].f-T[2*v].g,T[2*v+1].f-T[2*v+1].g);
}

int query(int l, int r, int v) {
	if(l==r) {
		return l;
	}
	propagate(v);
	int mid = (l+r)/2,w=-1;
	if(T[2*v].f-T[2*v].g==0) {
		w = query(l,mid,v*2);
	} else {
		w = query(mid+1,r,v*2+1);
	}
	T[v].f = min(T[2*v].f-T[2*v].g,T[2*v+1].f-T[2*v+1].g);
	return w;
}

void coutTree(int l,int r,int v) {
	if(l==r) {
		cout<<l<<" "<<l<<" : "<<T[l].f<<" "<<T[l].g<<"\n";
		return;
	}
	int mid = (l+r)/2;
	coutTree(l,mid,v*2);
	coutTree(mid+1,r,v*2+1);
	cout<<l<<" "<<r<<" : "<<T[l].f<<" "<<T[r].g<<"\n";
}

int main() {_
	cin>>n>>q;
	for(int j=0; j<3; j++) {
		for(int i=1; i<=n; i++) {
			cin>>t[j][i];
			ord[j][t[j][i]] = i;
		}
	}
	init(1,n,1);
	for(int i=1; i<=n; i++) {
		update(last(i),n,1,n,1,1);
	}
	while(q--) {
		int typ,a,b,c;
		cin>>typ;
		if(typ==1) {
			cin>>a;
			int tmp = query(1,n,1);
			//cout<<tmp<<" ";
			cout<<(last(a)>tmp?"NE\n":"DA\n");
		} else {
			cin>>c>>a>>b;
			update(last(a),n,1,n,1,-1);
			update(last(b),n,1,n,1,-1);
			swap(ord[c-1][a],ord[c-1][b]);
			update(last(a),n,1,n,1,1);
			update(last(b),n,1,n,1,1);
			//cout<<last(a)<<" "<<last(b)<<"\n";
		}
		//coutTree(1,n,1);
	}
	
}

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