Submission #938861

#	Time	Username	Problem	Language	Result	Execution time	Memory
938861		Lobo	Seats (IOI18_seats)	C++17	0 / 100	4017 ms	73160 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 = 200;

int n, m, col[maxn], row[maxn];
vector<pair<int,int>> mxB[maxn/B+10], mnB[maxn/B+10];
vector<int> vecmxmn[maxn/B+10];
// map<int,vector<int>> vecmn[maxn/B+10], vecmx[maxn/B+10];
vector<pair<int,int>> vecmn[maxn/B+10], vecmx[maxn/B+10];

void construct(int b) {
	int l = b*B;
	int r = min(n*m-1,(b+1)*B-1);
	int mx = -inf;
	int mn = inf;
	// B * log
	mxB[b].clear();
	mnB[b].clear();
	vecmxmn[b].clear();
	vecmn[b].clear();
	vecmx[b].clear();
	for(int k = l; k <= r; k++) {
		if(col[k] > mx) {
			mx = col[k];
			mxB[b].pb(mp(col[k],k)); // crescente
		}
		if(col[k] < mn) {
			mn = col[k];
			mnB[b].pb(mp(col[k],k)); // decrescente
		}
		if(mx-mn == k) {
			vecmxmn[b].pb(k);
		}
		if(mx-k >= 0 && mx-k < n*m) {
			vecmx[b].pb(mp(mx-k,k));
			// vecmx[b][mx-k].pb(k);
		}
		if(mn+k >= 0 && mn+k < n*m) {
			vecmn[b].pb(mp(mn+k,k));
			// vecmn[b][mn+k].pb(k);
		}
	}
	sort(all(vecmn[b]));
	sort(all(vecmx[b]));
	reverse(all(mnB[b])); // (crescente,decrescente)
}

int query() {
	int mx0 = -inf;
	int mn0 = inf;
	int ans = 0;

	// m/B * 4 log
	for(int b = 0; b*B < n*m; b++) {
		int l = b*B;
		int r = min(n*m-1,(b+1)*B-1);

		auto itmx = upper_bound(all(mxB[b]),mp(mx0,inf));
		int posmx;
		if(itmx != mxB[b].end()) posmx = itmx->sc;
		else posmx = r+1;

		auto itmn = upper_bound(all(mnB[b]),mp(mn0,inf));
		int posmn;
		if(itmn != mnB[b].begin()) posmn = prev(itmn)->sc;
		else posmn = r+1;

		// antes de mudar -> l ate min(posmn,posmx)-1
		if(mx0 != -inf && mn0 != inf && l <= mx0-mn0 && mx0-mn0 < min(posmn,posmx)) ans++;

		// depois de mudar os 2 -> max(posmn,posmx)
		ans+= vecmxmn[b].end() - lower_bound(all(vecmxmn[b]),max(posmn,posmx));

		if(posmx < posmn) {
			// posmx ate posmn-1
			// maxk - mn0 = k
			// maxk - k = mn0
			ans+= upper_bound(all(vecmx[b]),mp(mn0,posmn-1)) - lower_bound(all(vecmx[b]),mp(mn0,posmx));
			// ans+= upper_bound(all(vecmx[b][mn0]),posmn-1) - lower_bound(all(vecmx[b][mn0]),posmx);
		}
		else if(posmn < posmx) {
			ans+= upper_bound(all(vecmn[b]),mp(mx0,posmx-1)) - lower_bound(all(vecmn[b]),mp(mx0,posmn));
			// ans+= upper_bound(all(vecmn[b][mx0]),posmx-1) - lower_bound(all(vecmn[b][mx0]),posmn);
		}

		mn0 = min(mn0,mnB[b][0].fr);
		mx0 = max(mx0,mxB[b].back().fr);

		// cout << " " << l << " " << r << " " << ans << " " << posmn << " " << posmx << endl;
	}
	return ans;
}

void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) {
    n = H;
    m = W;
    for(int i = 0; i < n*m; i++) {
    	col[i] = C[i];
    	row[i] = R[i];
    }

    for(int i = 0; i*B < m; i++) {
    	construct(i);
    }
}

int32_t swap_seats(int32_t a, int32_t b) {
	swap(col[a],col[b]);
	construct(a/B); // B * log
	construct(b/B); // B * log
	return query(); // m/B * 4log
}

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