| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 120861 | faustaadp | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include<bits/stdc++.h>
typedef long long int;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int x[2][1010101],n,i,j;
int ST[2][2][4040404];
void upd(int aa,int bb,int cc,int dd,int ee)
{
if(aa==bb)
{
ST[0][dd][ee]=x[dd][aa];
ST[1][dd][ee]=x[dd][aa];
}
else
{
int ce=(aa+bb)/2;
if(cc<=ce)
upd(aa,ce,cc,dd,ee*2);
else
upd(ce+1,bb,cc,dd,ee*2+1);
ST[0][dd][ee]=min(ST[0][dd][ee*2],ST[0][dd][ee*2+1]);
ST[1][dd][ee]=max(ST[1][dd][ee*2],ST[1][dd][ee*2+1]);
}
}
int quemi(int aa,int bb,int cc,int dd,int ee,int ff)
{
if(bb<cc||dd<aa)
return 1e9;
else
if(cc<=aa&&bb<=dd)
return ST[0][ff][ee];
else
{
int ce=(aa+bb)/2;
return min(quemi(aa,ce,cc,dd,ee*2,ff),quemi(ce+1,bb,cc,dd,ee*2+1,ff));
}
}
int quema(int aa,int bb,int cc,int dd,int ee,int ff)
{
if(bb<cc||dd<aa)
return -1e9;
else
if(cc<=aa&&bb<=dd)
return ST[1][ff][ee];
else
{
int ce=(aa+bb)/2;
return max(quema(aa,ce,cc,dd,ee*2,ff),quema(ce+1,bb,cc,dd,ee*2+1,ff));
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
n=H*W;
for(i=0;i<H*W;i++)
{
x[0][i]=R[i];
x[1][i]=C[i];
upd(0,n-1,i,0,1);
upd(0,n-1,i,1,1);
}
}
int swap_seats(int a, int b)
{
swap(x[1][a],x[1][b]);
swap(x[0][a],x[0][b]);
upd(0,n-1,a,0,1);
upd(0,n-1,a,1,1);
upd(0,n-1,b,0,1);
upd(0,n-1,b,1,1);
int hz=0;
//cout<<"A";
//return 0;
int too=0;
for(i=0;i<n;i++)
{
too++;
int mx=quemi(0,n-1,0,i,1,0);
int my=quemi(0,n-1,0,i,1,1);
int Mx=quema(0,n-1,0,i,1,0);
int My=quema(0,n-1,0,i,1,1);
int tem=(Mx-mx+1)*(My-my+1);
if(tem==i+1)hz++;
// cout<<i<<" "<<tem<<"\n";
i=max(i,tem-2);
}
if(too>4020)n/=0;
return hz;
}