Submission #283849

#	Time	Username	Problem	Language	Result	Execution time	Memory
283849		AMO5	Tenis (COI19_tenis)	C++17	100 / 100	356 ms	7928 KiB

tenis

//modified from koosaga'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];
int pos[3][mxn];

int 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){
	int x = lazy[id];
	lazy[id]=0;
	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=1, int ri=n-1){
	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=1, int ri=n-1){
	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=1, int ri=n-1){
	cerr<<id<<" "<<le<<" "<<ri<<" : "<<tree[id]<<"\n";
	if(le==ri)return;
	int mid=(le+ri)/2;
	run(id*2,le,mid);
	run(id*2+1,mid+1,ri);
	return;
}

int main()
{
    scanf("%d %d",&n,&q);
    for(int i=0; i<3; i++){
		for(int j=1; j<=n; j++){
			scanf("%d",&a[i][j]);
			pos[i][a[i][j]]=j;
		}
	}
	for(int i=1; i<=n; i++){
		add(i,+1);
	}
	//run();
	while(q--){
		int typ;
		scanf("%d",&typ);
		if(typ==1){
			int x; 
			scanf("%d",&x); 
			int mn = min({pos[0][x],pos[1][x],pos[2][x]});
			//cerr<<"checking 0 "<<mn-1<<"\n";
			//cerr<<query(1,mn-1,1,1,n-1)<<"\n";
			puts(query(1,mn-1)?"DA":"NE");
		}else{
			int p,x,y;
			scanf("%d %d %d",&p,&x,&y);
			p--; 
			add(x,-1); add(y,-1);
			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 (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
tenis.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |    scanf("%d",&a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~
tenis.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   scanf("%d",&typ);
      |   ~~~~~^~~~~~~~~~~
tenis.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
tenis.cpp:118:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |    scanf("%d %d %d",&p,&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~

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