| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938790 | Lobo | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<pair<int,int>> mxB[maxn/B+10], mnB[maxn/B+10];
vector<int> vecmxmn[maxn/B+10];
unordered_map<int,vector<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
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][mx-k].pb(k);
}
if(mn+k >= 0 && mn+k < n*m) {
vecmn[b][mn+k].pb(k);
}
}
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;
// 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][mn0]),posmn-1) - lower_bound(all(vecmx[b][mn0]),posmx);
}
else if(posmn < posmx) {
ans+= upper_bound(all(vecmn[b][mx0]),posmx-1) - lower_bound(all(vecmn[b][mx0]),posmn);
}
mn0 = min(mn0,mnB[b][0]);
mx0 = max(mx0,mxb[b].back());
}
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
}