Submission #421679

#	Time	Username	Problem	Language	Result	Execution time	Memory
421679		alishahali1382	Seats (IOI18_seats)	C++14	17 / 100	4085 ms	59260 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pi4;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=1000010, LOG=18;

pi4 combine(pi4 a, pi4 b){ return {{min(a.first.first, b.first.first), min(a.first.second, b.first.second)}, {max(a.second.first, b.second.first), max(a.second.second, b.second.second)}};}

int n, m, k, H, W, x, y, t, ans;
int ok[MAXN];
pii A[MAXN];
pi4 seg[MAXN<<1];

void Set(int pos, pi4 x){
	for (seg[pos+=MAXN]=x; pos>1; pos>>=1) seg[pos>>1]=combine(seg[pos], seg[pos^1]);
}
pi4 Get(int l, int r){
	pi4 res=seg[0];
	for (l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
		if (l&1) res=combine(res, seg[l++]);
		if (r&1) res=combine(res, seg[--r]);
	}
	return res;
}
int getS(pi4 x){
	return (x.second.first-x.first.first+1)*(x.second.second-x.first.second+1);
}
void give_initial_chart(int _H, int _W, vi R, vi C) {
	H=_H;
	W=_W;
	n=H*W;
	fill(seg, seg+MAXN*2, pi4(pii(inf, inf), pii(-1, -1)));
	for (int i=0; i<n; i++){
		A[i]={R[i], C[i]};
		Set(i, {A[i], A[i]});
		ans+=(ok[i]=(getS(seg[1])==i+1));
	}
}
int swap_seats(int a, int b){
	if (a>b) swap(a, b);
	swap(A[a], A[b]);
	Set(a, {A[a], A[a]});
	Set(b, {A[b], A[b]});
	pi4 curr=Get(0, a);
	for (int i=a; i<b; i++){
		curr=combine(curr, pi4(A[i], A[i]));
		ans-=ok[i];
		ok[i]=(getS(curr)==i+1);
		ans+=ok[i];
	}
	return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

*/

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30