oj.uz

답안 #936612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936612 2024-03-02T11:34:13 Z Trisanu_Das 자리 배치 (IOI18_seats) C++17
100 / 100
 2191 ms 53072 KB 
#include "seats.h"
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k;
int posx[1000001],posy[1000001];
int num[1000001];
int minv[2097152],minc[2097152];
int lazy[2097152];
int a[5];
void build(int id,int l,int r){
	minc[id]=r-l+1;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
}
void supd(int id,int l,int r,int ll,int rr,int v){
	if(l>rr || r<ll) return;
	if(ll<=l && r<=rr){
		lazy[id]+=v;
		minv[id]+=v;
		return;
	}
	int mid=(l+r)/2;
	supd(id*2,l,mid,ll,rr,v);
	supd(id*2+1,mid+1,r,ll,rr,v);
	if(minv[id*2]<minv[id*2+1]) minv[id]=minv[id*2],minc[id]=minc[id*2];
	else if(minv[id*2]>minv[id*2+1]) minv[id]=minv[id*2+1],minc[id]=minc[id*2+1];
	else minv[id]=minv[id*2],minc[id]=minc[id*2]+minc[id*2+1];
	minv[id]+=lazy[id];
	return;
}
int get(int x,int y){
	if(x<0 || x>=n || y<0 || y>=m) return n*m;
	else return num[x*m+y];
}
void upd(int x,int y,int v){
	for(int i=0; i<2 ;i++)
		for(int j=0; j<2 ;j++)
			a[i+i+j]=get(x-i,y-j);
	sort(a,a+4);
	//cout << "UPD " << x << ' ' << y << ' ' << a[1] << ' ' << a[2] << ' ' << a[3] << ' ' << a[4] << ' ' << v << endl;;
	if(a[0]<a[1]) supd(1,0,k-1,a[0],a[1]-1,v);
	if(a[2]<a[3]) supd(1,0,k-1,a[2],a[3]-1,v);
}
void change(int x,int y,int v){
 	for(int i=0; i<2 ;i++)
		for(int j=0; j<2 ;j++)
			upd(x+i,y+j,-1);
	num[x*m+y]=v;
	for(int i=0; i<2 ;i++)
		for(int j=0; j<2 ;j++)
			upd(x+i,y+j,1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n=H;
	m=W;
	k=n*m;
	build(1,0,k-1);
	for(int i=0; i<k ;i++){
		posx[i]=R[i];
		posy[i]=C[i];
		num[posx[i]*m+posy[i]]=i;
	}
	for(int i=0; i<=n ;i++)
		for(int j=0; j<=m ;j++)
			upd(i,j,1);
}
 
int swap_seats(int a, int b) {
	change(posx[a],posy[a],b);
	change(posx[b],posy[b],a);
	swap(posx[a],posx[b]);
	swap(posy[a],posy[b]);
	return minc[1];//minv must be 4
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10584 KB Output is correct
2 Correct 17 ms 10776 KB Output is correct
3 Correct 23 ms 10588 KB Output is correct
4 Correct 15 ms 10588 KB Output is correct
5 Correct 12 ms 10588 KB Output is correct
6 Correct 19 ms 10752 KB Output is correct
7 Correct 21 ms 10588 KB Output is correct
8 Correct 19 ms 10776 KB Output is correct
9 Correct 19 ms 10588 KB Output is correct
10 Correct 21 ms 10752 KB Output is correct
11 Correct 21 ms 10584 KB Output is correct
12 Correct 12 ms 10584 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10584 KB Output is correct
2 Correct 17 ms 10776 KB Output is correct
3 Correct 23 ms 10588 KB Output is correct
4 Correct 15 ms 10588 KB Output is correct
5 Correct 12 ms 10588 KB Output is correct
6 Correct 19 ms 10752 KB Output is correct
7 Correct 21 ms 10588 KB Output is correct
8 Correct 19 ms 10776 KB Output is correct
9 Correct 19 ms 10588 KB Output is correct
10 Correct 21 ms 10752 KB Output is correct
11 Correct 21 ms 10584 KB Output is correct
12 Correct 12 ms 10584 KB Output is correct
13 Correct 53 ms 10844 KB Output is correct
14 Correct 55 ms 11008 KB Output is correct
15 Correct 32 ms 11016 KB Output is correct
16 Correct 22 ms 10840 KB Output is correct
17 Correct 39 ms 11012 KB Output is correct
18 Correct 41 ms 11000 KB Output is correct
19 Correct 36 ms 10844 KB Output is correct
20 Correct 30 ms 10844 KB Output is correct
21 Correct 23 ms 11020 KB Output is correct
22 Correct 23 ms 10840 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1337 ms 52492 KB Output is correct
2 Correct 646 ms 52488 KB Output is correct
3 Correct 685 ms 52288 KB Output is correct
4 Correct 553 ms 52564 KB Output is correct
5 Correct 564 ms 52292 KB Output is correct
6 Correct 520 ms 52304 KB Output is correct
7 Correct 597 ms 52564 KB Output is correct
8 Correct 672 ms 52456 KB Output is correct
9 Correct 633 ms 52488 KB Output is correct
10 Correct 600 ms 52488 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 11016 KB Output is correct
2 Correct 105 ms 20348 KB Output is correct
3 Correct 556 ms 52308 KB Output is correct
4 Correct 1342 ms 52548 KB Output is correct
5 Correct 519 ms 50260 KB Output is correct
6 Correct 1154 ms 52556 KB Output is correct
7 Correct 556 ms 52344 KB Output is correct
8 Correct 649 ms 52564 KB Output is correct
9 Correct 625 ms 51528 KB Output is correct
10 Correct 602 ms 52464 KB Output is correct
11 Correct 546 ms 51284 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 11656 KB Output is correct
2 Correct 69 ms 11600 KB Output is correct
3 Correct 107 ms 11612 KB Output is correct
4 Correct 156 ms 11676 KB Output is correct
5 Correct 235 ms 12508 KB Output is correct
6 Correct 824 ms 51788 KB Output is correct
7 Correct 946 ms 52820 KB Output is correct
8 Correct 792 ms 50764 KB Output is correct
9 Correct 1700 ms 52844 KB Output is correct
10 Correct 785 ms 51788 KB Output is correct
11 Correct 779 ms 52676 KB Output is correct
12 Correct 750 ms 50804 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10584 KB Output is correct
2 Correct 17 ms 10776 KB Output is correct
3 Correct 23 ms 10588 KB Output is correct
4 Correct 15 ms 10588 KB Output is correct
5 Correct 12 ms 10588 KB Output is correct
6 Correct 19 ms 10752 KB Output is correct
7 Correct 21 ms 10588 KB Output is correct
8 Correct 19 ms 10776 KB Output is correct
9 Correct 19 ms 10588 KB Output is correct
10 Correct 21 ms 10752 KB Output is correct
11 Correct 21 ms 10584 KB Output is correct
12 Correct 12 ms 10584 KB Output is correct
13 Correct 53 ms 10844 KB Output is correct
14 Correct 55 ms 11008 KB Output is correct
15 Correct 32 ms 11016 KB Output is correct
16 Correct 22 ms 10840 KB Output is correct
17 Correct 39 ms 11012 KB Output is correct
18 Correct 41 ms 11000 KB Output is correct
19 Correct 36 ms 10844 KB Output is correct
20 Correct 30 ms 10844 KB Output is correct
21 Correct 23 ms 11020 KB Output is correct
22 Correct 23 ms 10840 KB Output is correct
23 Correct 1337 ms 52492 KB Output is correct
24 Correct 646 ms 52488 KB Output is correct
25 Correct 685 ms 52288 KB Output is correct
26 Correct 553 ms 52564 KB Output is correct
27 Correct 564 ms 52292 KB Output is correct
28 Correct 520 ms 52304 KB Output is correct
29 Correct 597 ms 52564 KB Output is correct
30 Correct 672 ms 52456 KB Output is correct
31 Correct 633 ms 52488 KB Output is correct
32 Correct 600 ms 52488 KB Output is correct
33 Correct 45 ms 11016 KB Output is correct
34 Correct 105 ms 20348 KB Output is correct
35 Correct 556 ms 52308 KB Output is correct
36 Correct 1342 ms 52548 KB Output is correct
37 Correct 519 ms 50260 KB Output is correct
38 Correct 1154 ms 52556 KB Output is correct
39 Correct 556 ms 52344 KB Output is correct
40 Correct 649 ms 52564 KB Output is correct
41 Correct 625 ms 51528 KB Output is correct
42 Correct 602 ms 52464 KB Output is correct
43 Correct 546 ms 51284 KB Output is correct
44 Correct 36 ms 11656 KB Output is correct
45 Correct 69 ms 11600 KB Output is correct
46 Correct 107 ms 11612 KB Output is correct
47 Correct 156 ms 11676 KB Output is correct
48 Correct 235 ms 12508 KB Output is correct
49 Correct 824 ms 51788 KB Output is correct
50 Correct 946 ms 52820 KB Output is correct
51 Correct 792 ms 50764 KB Output is correct
52 Correct 1700 ms 52844 KB Output is correct
53 Correct 785 ms 51788 KB Output is correct
54 Correct 779 ms 52676 KB Output is correct
55 Correct 750 ms 50804 KB Output is correct
56 Correct 94 ms 11644 KB Output is correct
57 Correct 213 ms 11508 KB Output is correct
58 Correct 357 ms 12344 KB Output is correct
59 Correct 1119 ms 52732 KB Output is correct
60 Correct 2191 ms 53072 KB Output is correct
61 Correct 1056 ms 52824 KB Output is correct
62 Correct 840 ms 50756 KB Output is correct
63 Correct 1938 ms 53060 KB Output is correct
64 Correct 1277 ms 52820 KB Output is correct
65 Correct 1061 ms 52564 KB Output is correct
66 Correct 1193 ms 51804 KB Output is correct
67 Correct 1173 ms 52820 KB Output is correct
68 Correct 949 ms 52696 KB Output is correct
69 Correct 1694 ms 52844 KB Output is correct