oj.uz

답안 #111180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111180 2019-05-14T02:15:22 Z kig9981 자리 배치 (IOI18_seats) C++17
100 / 100
 3542 ms 78200 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include "seats.h"
 
using namespace std;
 
const int SZ=1<<20, dx[]={-1,0,1,0}, dy[]={0,-1,0,1};
vector<pair<int,int>> P;
pair<int,int> tree[2*SZ], lazy[2*SZ];
int N, M, tcnt[2*SZ], idx[1000000];
 
void lazy_propagation(int bit, int s, int e)
{
	tree[bit].first+=lazy[bit].first;
	tree[bit].second+=lazy[bit].second;
	if(s<e) {
		lazy[2*bit].first+=lazy[bit].first;
		lazy[2*bit].second+=lazy[bit].second;
		lazy[2*bit+1].first+=lazy[bit].first;
		lazy[2*bit+1].second+=lazy[bit].second;
	}
	lazy[bit]={0,0};
}
 
void add_tree(int n, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(e<n) return;
	if(n<=s) {
		tree[bit].first+=v.first;
		tree[bit].second+=v.second;
		if(s<e) {
			lazy[2*bit].first+=v.first;
			lazy[2*bit].second+=v.second;
			lazy[2*bit+1].first+=v.first;
			lazy[2*bit+1].second+=v.second;
		}
		return;
	}
	add_tree(n,v,2*bit,s,m);
	add_tree(n,v,2*bit+1,m+1,e);
	tree[bit]=min(tree[2*bit],tree[2*bit+1]);
	tcnt[bit]=(tree[bit]==tree[2*bit] ? tcnt[2*bit]:0)+(tree[bit]==tree[2*bit+1] ? tcnt[2*bit+1]:0);
}
 
bool valid_coord(int x, int y)
{
	return 0<=x && x<N && 0<=y && y<M;
}
 
int &convert(int x, int y)
{
	return idx[x*M+y];
}
 
pair<int,int> get_corner(int x, int y, int i)
{
	pair<int,int> ret;
	for(int k=0;k<4;k++) {
		if(valid_coord(x+dx[k],y+dy[k]) && valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) && convert(x+dx[k],y+dy[k])<=i && convert(x+dx[(k+1)&3],y+dy[(k+1)&3])<=i && convert(x,y)>i) {
			ret.second++;
		}
		else if((!valid_coord(x+dx[k],y+dy[k]) || convert(x+dx[k],y+dy[k])>i) && (!valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) || convert(x+dx[(k+1)&3],y+dy[(k+1)&3])>i) && convert(x,y)<=i) {
			ret.first++;
		}
	}
	return ret;
}
 
pair<int,int> get_diff(int i)
{
	pair<int,int> ret, temp;
	int x=P[i].first, y=P[i].second;
	temp=get_corner(x,y,i); ret.first+=temp.first; ret.second+=temp.second;
	temp=get_corner(x,y,i-1); ret.first-=temp.first; ret.second-=temp.second;
	for(int k=0;k<4;k++) if(valid_coord(x+dx[k],y+dy[k])) {
		temp=get_corner(x+dx[k],y+dy[k],i); ret.first+=temp.first; ret.second+=temp.second;
		temp=get_corner(x+dx[k],y+dy[k],i-1); ret.first-=temp.first; ret.second-=temp.second;
	}
	return ret;
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	P.resize(H*W);
	N=H; M=W;
	for(int i=0;i<H*W;i++) {
		P[i]={R[i],C[i]};
		convert(R[i],C[i])=i;
		tcnt[SZ+i]=1;
	}
	tree[SZ]=get_diff(0);
	for(int i=1;i<H*W;i++) {
		tree[SZ+i]=get_diff(i);
		tree[SZ+i].first+=tree[SZ+i-1].first;
		tree[SZ+i].second+=tree[SZ+i-1].second;
	}
	for(int i=H*W;i<SZ;i++) tree[SZ+i]=make_pair(0x1fffffff,0x1fffffff);
	for(int i=SZ-1;i;i--) {
		tree[i]=min(tree[2*i],tree[2*i+1]);
		tcnt[i]=(tree[i]==tree[2*i] ? tcnt[2*i]:0)+(tree[i]==tree[2*i+1] ? tcnt[2*i+1]:0);
	}
}
 
int swap_seats(int a, int b)
{
	pair<int,int> temp;
	int x1=P[a].first, y1=P[a].second, x2=P[b].first, y2=P[b].second;
	set<int> C;
	for(int dx=-1;dx<2;dx++) for(int dy=-1;dy<2;dy++) {
		if(valid_coord(x1+dx,y1+dy)) C.insert(convert(x1+dx,y1+dy));
		if(valid_coord(x2+dx,y2+dy)) C.insert(convert(x2+dx,y2+dy));
	}
	for(auto c: C) {
		temp=get_diff(c); temp.first*=-1; temp.second*=-1;
		add_tree(c,temp);
	}
	swap(P[a],P[b]);
	swap(convert(P[a].first,P[a].second),convert(P[b].first,P[b].second));
	for(auto c: C) add_tree(c,get_diff(c));
	return tcnt[1];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 21112 KB Output is correct
2 Correct 140 ms 21112 KB Output is correct
3 Correct 155 ms 20984 KB Output is correct
4 Correct 63 ms 20992 KB Output is correct
5 Correct 77 ms 21112 KB Output is correct
6 Correct 116 ms 21112 KB Output is correct
7 Correct 153 ms 20992 KB Output is correct
8 Correct 141 ms 21112 KB Output is correct
9 Correct 145 ms 21112 KB Output is correct
10 Correct 146 ms 21112 KB Output is correct
11 Correct 127 ms 21156 KB Output is correct
12 Correct 66 ms 21020 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 21112 KB Output is correct
2 Correct 140 ms 21112 KB Output is correct
3 Correct 155 ms 20984 KB Output is correct
4 Correct 63 ms 20992 KB Output is correct
5 Correct 77 ms 21112 KB Output is correct
6 Correct 116 ms 21112 KB Output is correct
7 Correct 153 ms 20992 KB Output is correct
8 Correct 141 ms 21112 KB Output is correct
9 Correct 145 ms 21112 KB Output is correct
10 Correct 146 ms 21112 KB Output is correct
11 Correct 127 ms 21156 KB Output is correct
12 Correct 66 ms 21020 KB Output is correct
13 Correct 235 ms 21468 KB Output is correct
14 Correct 198 ms 21624 KB Output is correct
15 Correct 68 ms 21496 KB Output is correct
16 Correct 74 ms 21496 KB Output is correct
17 Correct 168 ms 21496 KB Output is correct
18 Correct 179 ms 21504 KB Output is correct
19 Correct 155 ms 21504 KB Output is correct
20 Correct 107 ms 21500 KB Output is correct
21 Correct 66 ms 21596 KB Output is correct
22 Correct 72 ms 21572 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1338 ms 60264 KB Output is correct
2 Correct 740 ms 60316 KB Output is correct
3 Correct 711 ms 60132 KB Output is correct
4 Correct 775 ms 60244 KB Output is correct
5 Correct 783 ms 60296 KB Output is correct
6 Correct 886 ms 60360 KB Output is correct
7 Correct 839 ms 60104 KB Output is correct
8 Correct 829 ms 60260 KB Output is correct
9 Correct 880 ms 60108 KB Output is correct
10 Correct 719 ms 60212 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 21500 KB Output is correct
2 Correct 278 ms 24568 KB Output is correct
3 Correct 770 ms 60136 KB Output is correct
4 Correct 1394 ms 60248 KB Output is correct
5 Correct 503 ms 59492 KB Output is correct
6 Correct 758 ms 60208 KB Output is correct
7 Correct 620 ms 60220 KB Output is correct
8 Correct 725 ms 60356 KB Output is correct
9 Correct 893 ms 60388 KB Output is correct
10 Correct 838 ms 60260 KB Output is correct
11 Correct 553 ms 59748 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 21980 KB Output is correct
2 Correct 406 ms 21932 KB Output is correct
3 Correct 426 ms 21988 KB Output is correct
4 Correct 452 ms 22004 KB Output is correct
5 Correct 435 ms 22480 KB Output is correct
6 Correct 1032 ms 61280 KB Output is correct
7 Correct 1070 ms 61288 KB Output is correct
8 Correct 957 ms 61412 KB Output is correct
9 Correct 1327 ms 61340 KB Output is correct
10 Correct 939 ms 61320 KB Output is correct
11 Correct 858 ms 61256 KB Output is correct
12 Correct 961 ms 61304 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 21112 KB Output is correct
2 Correct 140 ms 21112 KB Output is correct
3 Correct 155 ms 20984 KB Output is correct
4 Correct 63 ms 20992 KB Output is correct
5 Correct 77 ms 21112 KB Output is correct
6 Correct 116 ms 21112 KB Output is correct
7 Correct 153 ms 20992 KB Output is correct
8 Correct 141 ms 21112 KB Output is correct
9 Correct 145 ms 21112 KB Output is correct
10 Correct 146 ms 21112 KB Output is correct
11 Correct 127 ms 21156 KB Output is correct
12 Correct 66 ms 21020 KB Output is correct
13 Correct 235 ms 21468 KB Output is correct
14 Correct 198 ms 21624 KB Output is correct
15 Correct 68 ms 21496 KB Output is correct
16 Correct 74 ms 21496 KB Output is correct
17 Correct 168 ms 21496 KB Output is correct
18 Correct 179 ms 21504 KB Output is correct
19 Correct 155 ms 21504 KB Output is correct
20 Correct 107 ms 21500 KB Output is correct
21 Correct 66 ms 21596 KB Output is correct
22 Correct 72 ms 21572 KB Output is correct
23 Correct 1338 ms 60264 KB Output is correct
24 Correct 740 ms 60316 KB Output is correct
25 Correct 711 ms 60132 KB Output is correct
26 Correct 775 ms 60244 KB Output is correct
27 Correct 783 ms 60296 KB Output is correct
28 Correct 886 ms 60360 KB Output is correct
29 Correct 839 ms 60104 KB Output is correct
30 Correct 829 ms 60260 KB Output is correct
31 Correct 880 ms 60108 KB Output is correct
32 Correct 719 ms 60212 KB Output is correct
33 Correct 176 ms 21500 KB Output is correct
34 Correct 278 ms 24568 KB Output is correct
35 Correct 770 ms 60136 KB Output is correct
36 Correct 1394 ms 60248 KB Output is correct
37 Correct 503 ms 59492 KB Output is correct
38 Correct 758 ms 60208 KB Output is correct
39 Correct 620 ms 60220 KB Output is correct
40 Correct 725 ms 60356 KB Output is correct
41 Correct 893 ms 60388 KB Output is correct
42 Correct 838 ms 60260 KB Output is correct
43 Correct 553 ms 59748 KB Output is correct
44 Correct 216 ms 21980 KB Output is correct
45 Correct 406 ms 21932 KB Output is correct
46 Correct 426 ms 21988 KB Output is correct
47 Correct 452 ms 22004 KB Output is correct
48 Correct 435 ms 22480 KB Output is correct
49 Correct 1032 ms 61280 KB Output is correct
50 Correct 1070 ms 61288 KB Output is correct
51 Correct 957 ms 61412 KB Output is correct
52 Correct 1327 ms 61340 KB Output is correct
53 Correct 939 ms 61320 KB Output is correct
54 Correct 858 ms 61256 KB Output is correct
55 Correct 961 ms 61304 KB Output is correct
56 Correct 637 ms 22120 KB Output is correct
57 Correct 1379 ms 21980 KB Output is correct
58 Correct 1519 ms 22408 KB Output is correct
59 Correct 2806 ms 61332 KB Output is correct
60 Correct 3542 ms 61456 KB Output is correct
61 Correct 2110 ms 77924 KB Output is correct
62 Correct 1649 ms 77960 KB Output is correct
63 Correct 3073 ms 78052 KB Output is correct
64 Correct 2729 ms 78072 KB Output is correct
65 Correct 2138 ms 78124 KB Output is correct
66 Correct 2928 ms 78200 KB Output is correct
67 Correct 2182 ms 77940 KB Output is correct
68 Correct 1815 ms 78052 KB Output is correct
69 Correct 2549 ms 78148 KB Output is correct