Submission #1111623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111623		epicci23	Seats (IOI18_seats)	C++17	11 / 100	4051 ms	24132 KiB

seats

#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;
  } 
};

int n,m;
vector<array<int,2>> go;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  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;
}*/

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