Submission #287930

#	Time	Username	Problem	Language	Result	Execution time	Memory
287930		Noam13	Seats (IOI18_seats)	C++14	17 / 100	4072 ms	262144 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;

vi add(vi& a, vi& b){
	vi res = a;
	loop(i,0,a.size()) res[i]+=b[i];
	return res;
}
void apply(vi& a, int x){
	loopr(i,0,a.size()-x){
		a[i+x] = a[i];
	}
	loop(i,0,x){
		if (i==a.size()) break;
		a[i] = 0;
	}
}
const vi basic = {1,0,0};
const int N = 1<<21;
int prop[N] = {0};
vi vecs[N] = {basic}, before[N] = {basic};

void setv(int cur){
	vecs[cur] = before[cur];
	if (prop[cur]>0) apply(vecs[cur], prop[cur]);
}
void pull(int cur){
	int dx = min(prop[2*cur], prop[2*cur+1]);
	if (dx){
		prop[2*cur]-=dx; prop[2*cur+1]-=dx; prop[cur]+=dx;
		setv(2*cur); setv(2*cur+1);
	}
	before[cur] = add(vecs[2*cur], vecs[2*cur+1]);
	setv(cur);
}
void build(int cur, int l, int r, vi& a){
	if (l+1==r){
		before[cur] = basic;
		prop[cur] = a[l];
		setv(cur);
		return ;
	}
	int mid = (l+r)/2;
	build(2*cur, l, mid, a);
	build(2*cur+1, mid, r, a);
	pull(cur);
}
void update(int cur, int l, int r, int a, int b, int v){
	if (a>=r || b<=l) return ;
	//cout<<"CUR: "<<cur<<" "<<l<<" "<<r<<endl;
	if (a<=l && r<=b){
		prop[cur]+=v;
		if (l+1==r){
			before[cur] = basic;
			setv(cur);
		}
		else pull(cur);
		return ;
	}
	int mid = (l+r)/2;
	update(2*cur, l, mid, a,b,v);
	update(2*cur+1, mid, r, a,b,v);
	pull(cur);
}
int query(){
	return vecs[1][2];
}


int n;

vi vals;
vi pos;
void update(int i, int v){
	int a = vals[i], b = vals[i+1];
	if (a>b) swap(a,b);
	update(1,0,n,a,b,v);
}
struct Rec{
	int lx, rx, ly, ry;
};
Rec uni(const Rec& a, const Rec& b){
	return {min(a.lx, b.lx), max(a.rx, b.rx),
			min(a.ly, b.ly), max(a.ry, b.ry)};
}
int val(const Rec& a){
	return (a.rx-a.lx+1)*(a.ry-a.ly+1);
}
Rec get(int i, int j){
	return {i,i,j,j};
}
int m;
vector<Rec> recs;
vb valss; int sum = 0;
vi r,c;
void update(int i){
	sum-=valss[i+1];
	recs[i+1] = uni(recs[i], get(r[i], c[i]));
	valss[i+1] = (val(recs[i+1])==i+1);
	sum+=valss[i+1];
}
bool state = 0;
void give_initial_chart(int H, int W, vi R, vi C) {
	if (H>1){
		n = H, m = W;
		recs.resize(n*m+1, {INF, -INF, INF, -INF});
		valss.resize(n*m+1,0);
		r = R, c = C;
		loop(i,0,n*m){
			update(i);
		}
	}
	else{
		state = 1;
		n = W;
		vals.resize(n+2, n); pos = C;
		loop(i,0,n) pos[i]++;
		loop(i,0,n) vals[pos[i]] = i;
		vi pref(n+1);
		loop(i,0,n+1){
			int a = vals[i], b = vals[i+1];
			if (a>b) swap(a,b);
			pref[a]++; pref[b]--;
			//update(i, 1);
		}
		loop(i,1,n) pref[i]+=pref[i-1];
		//loop(i,0,n) cout<<pref[i]<<" "; cout<<endl;
		build(1, 0, n, pref);
	}
}
set<int> working;
void Working(int a){
    working.insert(a);
	working.insert(a-1);
}
int swap_seats(int a, int b) {
	if (state){
		swap(pos[a], pos[b]);
		a = pos[a], b = pos[b];
		working.clear();
		Working(a); Working(b);
		for(auto x:working) update(x,-1);
		swap(vals[a], vals[b]);
		for(auto x:working) update(x,1);
		return query();
	}
	if (a>b) swap(a,b);
	swap(r[a], r[b]); swap(c[a], c[b]);
	loop(i,a,b+1){
		update(i);
	}
	return sum;
}
/*
clear
g++ seats.cpp grader.cpp -o a ; ./a
1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0
*/

Compilation message (stderr)

seats.cpp: In function 'std::vector<int> add(std::vector<int>&, std::vector<int>&)':
seats.cpp:6:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define loop(i,s,e) for(int i=s;i<e;i++)
......
   21 |  loop(i,0,a.size()) res[i]+=b[i];
      |       ~~~~~~~~~~~~                
seats.cpp:21:2: note: in expansion of macro 'loop'
   21 |  loop(i,0,a.size()) res[i]+=b[i];
      |  ^~~~
seats.cpp: In function 'void apply(std::vector<int>&, int)':
seats.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if (i==a.size()) break;
      |       ~^~~~~~~~~~

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