Submission #943741

#	Time	Username	Problem	Language	Result	Execution time	Memory
943741		Lobo	Seats (IOI18_seats)	C++17	0 / 100	1787 ms	110708 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
const int B = 1000;

int n, m, col[maxn], row[maxn];
vector<vector<int>> grid;
int trmn[4*maxn], trq[4*maxn], lz[4*maxn];

void build(int no, int l, int r) {
	trq[no] = r-l+1;
	trmn[no] = 0;
	if(l == r) return;
	int lc=2*no,rc=2*no+1,mid=(l+r)/2;
	build(lc,l,mid);
	build(rc,mid+1,r);
}

void flush(int no, int l, int r) {
	trmn[no]+= lz[no];

	if(l != r) {
		int lc=2*no,rc=2*no+1;
		lz[lc]+= lz[no];
		lz[rc]+= lz[no];
	}
	lz[no] = 0;
}

void upd(int no, int l, int r, int ll, int rr, int val) {
	flush(no,l,r);
	if(l > rr or r < ll) return;
	if(l >= ll && r <= rr) {
		lz[no] = val;
		flush(no,l,r);
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)/2;
	upd(lc,l,mid,ll,rr,val);
	upd(rc,mid+1,r,ll,rr,val);
	trmn[no] = min(trmn[lc],trmn[rc]);
	trq[no] = 0;
	if(trmn[no] == trmn[lc]) trq[no]+= trq[lc];
	if(trmn[no] == trmn[rc]) trq[no]+= trq[rc];
}

void construct(int i, int j, int dx) {
	vector<int> times;

	for(int di = 0; di <= 1; di++) {
		for(int dj = 0; dj <= 1; dj++) {
			if(i+di >= 0 && i+di < n && j+dj >= 0 && j+dj < m) {
				times.pb(grid[i+di][j+dj]);
			}
		}
	}
	sort(all(times));

	for(int i = 0; i < (int) times.size(); i++) {
		int tl = times[i];
		int tr;
		if(i+1 < (int) times.size()) tr = times[i+1]-1;
		else tr = n*m-1;
		if(i+1 == 1) upd(1,0,n*m-1,tl,tr,+1*dx);
		if(i+1 == 3) upd(1,0,n*m-1,tl,tr,+5*dx);
	}
}

void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) {
    n = H;
    m = W;
    grid.resize(n,vector<int>(m));
    for(int i = 0; i < n*m; i++) {
    	col[i] = C[i];
    	row[i] = R[i];
    	grid[row[i]][col[i]] = i;
    }
    build(1,0,n*m-1);
    for(int i = -1; i < n; i++) {
    	for(int j = -1; j < m; j++) {
    		construct(i,j,1);
    	}
    }
}

int32_t swap_seats(int32_t a, int32_t b) {
	int i,j;
	set<pair<int,int>> st;
	i = row[a];
	j = col[a];
	for(int di = 0; di <= 1; di++) {
		for(int dj = 0; dj <= 1; dj++) {
			if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
				st.insert(mp(i+di,j+dj));
			}
		}
	}
	i = row[b];
	j = col[b];
	for(int di = 0; di <= 1; di++) {
		for(int dj = 0; dj <= 1; dj++) {
			if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
				st.insert(mp(i+di,j+dj));
			}
		}
	}

	for(auto x : st) {
		construct(x.fr,x.sc,-1);
	}

	swap(col[a],col[b]);
	swap(row[a],row[b]);
	grid[row[a]][col[a]] = a;
	grid[row[b]][col[b]] = b;

	for(auto x : st) {
		construct(x.fr,x.sc,+1);
	}

	return trq[1];
}

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