Submission #287974

#	Time	Username	Problem	Language	Result	Execution time	Memory
287974		Noam13	Seats (IOI18_seats)	C++14	100 / 100	2711 ms	99556 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;

const int N = 1<<21;
int prop[N] = {0};
ii st[N];

void setp(int cur, int p){
	prop[cur]+=p;
	st[cur].x+=p;
}
void pull(int cur){
	st[cur] = {min(st[2*cur].x, st[2*cur+1].x),0};
	if (st[cur].x>=st[2*cur].x) st[cur].y+=st[2*cur].y;
	if (st[cur].x>=st[2*cur+1].x) st[cur].y+=st[2*cur+1].y;
}
void push(int cur){
	setp(2*cur, prop[cur]);
	setp(2*cur+1, prop[cur]);
	prop[cur] = 0;
}
void build(int cur, int l, int r, vi& a){
	if (l+1==r){
		st[cur] = {a[l],1};
		return ;
	}
	int mid = (l+r)/2;
	build(2*cur, l, mid, a);
	build(2*cur+1, mid, r, a);
	pull(cur);
}
bool flag = 0; vi pref;
void update(int cur, int l, int r, int a, int b, int v){
    if (!flag){
        pref[a]++; pref[b]--;
        return ;
    }
	if (a>=r || b<=l) return ;
	if (a<=l && r<=b){
		setp(cur, v);
		return ;
	}
	int mid = (l+r)/2;
	push(cur);
	update(2*cur, l, mid, a,b,v);
	update(2*cur+1, mid, r, a,b,v);
	pull(cur);
}
int query(){
	return st[1].y;
}

int n,m;

vvi vals;
vii pos;

void update(int i, int j, int v){
	vi vs;
	loop(a,0,2) loop(b,0,2) vs.pb(vals[i+a][j+b]);
	sort(all(vs));
    int a = vs[0], b = vs[1], c = vs[2], d = vs[3];
    update(1, 0, n*m, a, b, v);
    update(1, 0, n*m, c, d, v);
}
void give_initial_chart(int H, int W, vi R, vi C) {
	n = H, m = W;
	vals.resize(n+2, vi(m+2, n*m)); 
	pos.resize(n*m);
	loop(i,0,n*m) {
		pos[i] = {R[i]+1, C[i]+1};
	}
	loop(i,0,n*m) vals[pos[i].x][pos[i].y] = i;
    pref.resize(n*m+1,0);
	loop(i,0,n+1){
		loop(j,0,m+1){
			update(i, j, 1);
		}
	}
    loop(i,1,n*m) pref[i]+=pref[i-1];
    build(1,0,n*m, pref);
    flag = 1;
}
set<ii> working;
void Working(ii p){
	int a = p.x, b = p.y;
    working.insert({a,b});
    working.insert({a-1,b});
    working.insert({a,b-1});
    working.insert({a-1,b-1});
}
int swap_seats(int a, int b) {
	ii posa = pos[a], posb = pos[b];
    working.clear();
	Working(posa); Working(posb);
    for(auto p:working) update(p.x, p.y, -1);
	swap(vals[posa.x][posa.y], vals[posb.x][posb.y]);
	for(auto p:working) update(p.x, p.y, 1);
	swap(pos[a], pos[b]);
	return query();
}
/*
clear
g++ seats2.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
*/

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