제출 #106249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106249		tictaccat	Seats (IOI18_seats)	C++14	0 / 100	303 ms	39704 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,0); k <= min(H*2,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);
  update_chart(0,H*W-1);
}

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

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