Submission #808098

#	Time	Username	Problem	Language	Result	Execution time	Memory
808098		mindiyak	Seats (IOI18_seats)	C++14	0 / 100	4045 ms	47256 KiB

seats

#include "seats.h"
#include <iostream>
using namespace std;
 
const int MX = 1e6+5;
vector<pair<int,int>> pos(MX);
int n = 0;
vector<int> rmin(MX,0);
vector<int> rmax(MX,0);
vector<int> cmin(MX,0);
vector<int> cmax(MX,0);
vector<long long> temp_ans(MX,0);
 
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n = H*W;
  for(int i=0;i<H*W;i++)pos[i] = {R[i],C[i]};
 
  
  rmin[0]=rmax[0]=pos[0].first;
  cmin[0]=cmax[0]=pos[0].second;
 
  for(int i=1;i<n;i++){
    rmin[i] = min(rmin[i-1],pos[i].first);
    rmax[i] = max(rmax[i-1],pos[i].first);
 
    cmin[i] = min(cmin[i-1],pos[i].second);
    cmax[i] = max(cmax[i-1],pos[i].second);
  }
 
  long long ans = 0;
  for(int i=0;i<n;i++){
    int box_size = (rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1);
    // cout << "{" << rmin[i] << "," << rmax[i] << "} {" <<  cmin[i] << "," << cmax[i] << "} " <<  box_size << " " << i+1 << endl;
    if(i+1 == box_size){
      ans++;
    }
    temp_ans[i] = ans;
  }
}
 
 
int swap_seats(int a, int b) {
  swap(pos[a],pos[b]);
  long long ans = 0;
 
  if(a==0){
    rmin[0]=rmax[0]=pos[0].first;
    cmin[0]=cmax[0]=pos[0].second;
  }else{
    ans = temp_ans[a-1];
  }
  for(int i=max(a,1);i<=b;i++){
    rmin[i] = min(rmin[i-1],pos[i].first);
    rmax[i] = max(rmax[i-1],pos[i].first);
 
    cmin[i] = min(cmin[i-1],pos[i].second);
    cmax[i] = max(cmax[i-1],pos[i].second);
  }
 
  // cout << endl;
  int change = -temp_ans[b];
  for(int i=a;i<=b;i++){
    int box_size = (rmax[i]-rmin[i]+1)*(cmax[i]-cmin[i]+1);
    // cout << "{" << rmin[i] << "," << rmax[i] << "} {" <<  cmin[i] << "," << cmax[i] << "} " <<  box_size << " " << i+1 << endl;
    if(i+1 == box_size){
      change++;
      ans ++;
    }
    temp_ans[i]=ans;
  }for(int i=b+1;i<n;i++)temp_ans[i]+=change;
  // cout << " ans = " << ans << endl << endl;
 
  // for(int i=0;i<n;i++)cout << temp_ans[i] << " ";
  // cout << endl;
  return temp_ans[n-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