Submission #1035233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035233		huutuan	Seats (IOI18_seats)	C++14	17 / 100	4062 ms	60464 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int min_x[N], max_x[N], min_y[N], max_y[N];
pair<int, int> pos[N];
int check[N], sum;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
   for (int i=0; i<H*W; ++i){
      pos[i]={R[i], C[i]};
      if (!i) min_x[i]=max_x[i]=pos[i].first, min_y[i]=max_y[i]=pos[i].second;
      else{
         min_x[i]=min(min_x[i-1], pos[i].first);
         max_x[i]=max(max_x[i-1], pos[i].first);
         min_y[i]=min(min_y[i-1], pos[i].second);
         max_y[i]=max(max_y[i-1], pos[i].second);
      }
      check[i]=(max_x[i]-min_x[i]+1)*(max_y[i]-min_y[i]+1)==(i+1);
      sum+=check[i];
   }
}

int swap_seats(int a, int b) {
   if (a>b) swap(a, b);
   swap(pos[a], pos[b]);
   for (int i=a; i<b; ++i){
      sum-=check[i];
      if (!i) min_x[i]=max_x[i]=pos[i].first, min_y[i]=max_y[i]=pos[i].second;
      else{
         min_x[i]=min(min_x[i-1], pos[i].first);
         max_x[i]=max(max_x[i-1], pos[i].first);
         min_y[i]=min(min_y[i-1], pos[i].second);
         max_y[i]=max(max_y[i-1], pos[i].second);
      }
      check[i]=(max_x[i]-min_x[i]+1)*(max_y[i]-min_y[i]+1)==(i+1);
      sum+=check[i];
   }
   return sum;
}

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