# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1111622 | epicci23 | 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 "bits/stdc++.h"
#include "seats.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 1e6 + 5;
const int INF = (int) 1e9;
struct Fenwick{ // 1-indexed yap!!
vector<int> fw;
Fenwick(int _n,int _def){
fw.assign(_n,_def);
}
inline void upd(int c,int u){
for(;c<N;c+=c&-c) fw[c]+=u;
}
inline int query(int c,int res=0){
for(;c;c-=c&-c) res+=fw[c];
return res;
}
};
vector<array<int,2>> go;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
int n=H,m=W;
//Fenwick F(N,0);
go.resize(n*m+5);
for(int i=0;i<n*m;i++){
int a=R[i],b=C[i];
go[i]={a,b};
}
//int mnr[n*m+5],mxr[n*m+5],mnc[n*m+5],mxc[n*m+5];
/* int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
for(int i=0;i<n*m;i++){
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1) F.upd(i+1,1);
}*/
//cout << F.query(n*m) << '\n';
}
int swap_seats(int a, int b) {
int ans=0;
swap(go[a],go[b]);
int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
for(int i=0;i<n*m;i++){
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1) ans++;
}
return ans;
}
/*void _(){
int n,m,q;
cin >> n >> m >> q;
Fenwick F(N,0);
int ar[n+5][m+5];
array<int,2> go[n*m+5];
for(int i=0;i<n*m;i++){
int a,b;
cin >> a >> b;
ar[a][b]=i;
go[i]={a,b};
}
int mnr[n*m+5],mxr[n*m+5],mnc[n*m+5],mxc[n*m+5];
int Mnr=INF,Mxr=-INF,Mnc=INF,Mxc=-INF;
for(int i=0;i<n*m;i++){
int a = go[i][0] , b = go[i][1];
Mnr=min(Mnr,a);
Mxr=max(Mxr,a);
Mnc=min(Mnc,b);
Mxc=max(Mxc,b);
if((Mxc-Mnc+1)*(Mxr-Mnr+1)==i+1) F.upd(i+1,1);
}
cout << F.query(n*m) << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/