Submission #106253

#	Time	Username	Problem	Language	Result	Execution time	Memory
106253		tictaccat	Seats (IOI18_seats)	C++14	17 / 100	4078 ms	55816 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> R,C;
int H,W;
vector<bool> beautiful;
int beauty;

vector<int> ups,downs,lefts,rights;

void update_chart(int a, int b) {
  for (int k = max(a-3,1); k <= min(H*W,b+3); k++) {
    if (beautiful[k]) {
      beautiful[k] = false;
      beauty--;
    }
    ups[k] = min(ups[k-1],R[k-1]);
    downs[k] = max(downs[k-1],R[k-1]);
    lefts[k] = min(lefts[k-1],C[k-1]);
    rights[k] = max(rights[k-1],C[k-1]);
    //if (k == 3) cout << rights[k] << " " << lefts[k] << " " << downs[k] << " " <<  << "\n";
    if ((rights[k]-lefts[k]+1)*(downs[k]-ups[k]+1) == k) {
   //   cout << k << "\n";
      beautiful[k] = true;
      beauty++;
    }
  }
}

void give_initial_chart(int tempH, int tempW, std::vector<int> tempR, std::vector<int> tempC) {
  H = tempH; W = tempW; R = tempR; C = tempC;
  ups.resize(H*W+1,H); downs.resize(H*W+1,0); lefts.resize(H*W+1,H); rights.resize(H*W+1,0); beautiful.resize(H*W+1,false);
  lefts[0] = W; ups[0] = H;
  rights[0] = downs[0] = 0;  
  update_chart(0,H*W-1);
}

int swap_seats(int a, int b) {
  if (a > b) swap(a,b);
   swap(R[a],R[b]);
   swap(C[a],C[b]);
   update_chart(a,b);
  return beauty;
}

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