제출 #991368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991368		PCTprobability	자리 배치 (IOI18_seats)	C++17	17 / 100	4038 ms	55740 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int r[1010101],c[1010101];
int mr[1010101][2],mc[1010101][2];
int n,m;
int ans=0;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n=H,m=W;
  for(int i=0;i<n*m;i++){
    r[i]=R[i];
    c[i]=C[i];
    mr[i][0]=mr[i][1]=R[i];
    mc[i][0]=mc[i][1]=C[i];
  }
  for(int i=1;i<n*m;i++){
    mr[i][0]=min(mr[i][0],mr[i-1][0]);
    mr[i][1]=max(mr[i][1],mr[i-1][1]);
    mc[i][0]=min(mc[i][0],mc[i-1][0]);
    mc[i][1]=max(mc[i][1],mc[i-1][1]);
  }
  for(int i=0;i<n*m;i++){
    //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl;
    if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans++;
  }
}

int swap_seats(int a, int b) {
  if(a>b) swap(a,b);
  swap(r[a],r[b]);
  swap(c[a],c[b]);
  //cout<<a<<" "<<b<<endl;
  for(int i=a;i<b;i++){
    //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl;
    if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans--;
    if(i){
      mr[i][0]=min(r[i],mr[i-1][0]);
      mr[i][1]=max(r[i],mr[i-1][1]);
      mc[i][0]=min(c[i],mc[i-1][0]);
      mc[i][1]=max(c[i],mc[i-1][1]);
    }
    else{
      mr[i][0]=mr[i][1]=r[i];
      mc[i][0]=mc[i][1]=c[i];
    }
    //cout<<i<<" "<<r[i]<<" "<<c[i]<<" "<<mr[i][1]<<" "<<mr[i][0]<<" "<<mc[i][1]<<" "<<mc[i][0]<<" "<<(mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)<<endl;
    if((mr[i][1]-mr[i][0]+1)*(mc[i][1]-mc[i][0]+1)==i+1) ans++;
  }
  return ans;
}

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