oj.uz

답안 #936548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936548 2024-03-02T07:21:14 Z Trisanu_Das 자리 배치 (IOI18_seats) C++17
50 / 100
 4000 ms 99920 KB 
#include "seats.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
 
const int maxn = 1e6 + 20;
 
int n , a[maxn] , pos[maxn] , cnt[maxn * 4] , mn[maxn * 4] , Add[maxn * 4];
 
bool has[maxn];
 
int H , tx[maxn] , ty[maxn] , is[maxn] , SUM;
 
int mxxt[maxn] , mxyt[maxn] , mnxt[maxn] , mnyt[maxn];
 
void build(int s = 0 , int e = n , int v = 1)
{
	cnt[v] = e - s;
	if(e - s < 2)
		return;
 
	int m = (s + e) / 2;
	build(s , m , 2 * v);
	build(m , e , 2 * v + 1);
}
 
void add(int l , int r , int val , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
	{
		Add[v] += val;
		mn[v] += val;
		return;
	}
	if(r <= s || e <= l)
		return;
 
	int m = (s + e) / 2;
	add(l , r , val , s , m , 2 * v);
	add(l , r , val , m , e , 2 * v + 1);
 
	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
	cnt[v] = 0;
 
	if(mn[v] == mn[2 * v])
		cnt[v] += cnt[2 * v];
	if(mn[v] == mn[2 * v + 1])
		cnt[v] += cnt[2 * v + 1];
 
	mn[v] += Add[v];
}
 
void d(int k , int val)
{
	if(k <= 0 || k > n)
		return;
	if(val == -1 && !has[k])
		return;
	if(val == 1 && has[k])
		return;
 
	has[k] ^= 1;
	add(pos[k] , n , pos[k - 1] < pos[k]? -1 * val : 1 * val);
	add(pos[k] , n , pos[k + 1] < pos[k]? -1 * val : 1 * val);
}
 
void give_initial_chart(int HH, int W, vector<int> R, vector<int> C)
{
	H = HH;
	n = H * W;
	build();
	for(int i = 0; i < n; i++)
	{
		tx[i] = R[i] , ty[i] = C[i];
		a[i] = C[i] + 1;
		pos[a[i]] = i;
	}
	pos[0] = pos[n + 1] = 1e9;
 
	for(int i = 0; i < n; i++)
		d(a[i] , 1);
 
	int mnx = 1e9 , mny = 1e9 , mxx = -1 , mxy = -1;
	for(int i = 0; i < n; i++)
	{
		mnx = min(mnx , tx[i]);
		mny = min(mny , ty[i]);
 
		mxx = max(mxx , tx[i]);
		mxy = max(mxy , ty[i]);
 
		if((mxx - mnx + 1) * (mxy - mny + 1) == i + 1)
			SUM++ , is[i] = 1;
 
		mxxt[i] = mxx , mnxt[i] = mnx;
		mxyt[i] = mxy , mnyt[i] = mny;
	}
}
 
int swap_seats(int x, int y)
{
	if(H == 1)
	{
		for(int i = -1; i <= 1; i++)
			d(a[x] + i , -1) , d(a[y] + i , -1);
 
		swap(a[x] , a[y]);
		swap(pos[a[x]] , pos[a[y]]);
 
		for(int i = -1; i <= 1; i++)
			d(a[x] + i , 1) , d(a[y] + i , 1);
 
		return cnt[1];
	}
	else
	{
		swap(tx[x] , tx[y]);
		swap(ty[x] , ty[y]);
 
		int mnx = 1e9 , mny = 1e9 , mxx = -1 , mxy = -1;
		int k = min(x , y);
		if(k)
			mnx = mnxt[k - 1] , mxx = mxxt[k - 1] , mny = mnyt[k - 1] , mxy = mxyt[k - 1];
		for(int i = min(x , y); i <= max(x , y); i++)
		{
			SUM -= is[i];
			mnx = min(mnx , tx[i]);
			mny = min(mny , ty[i]);
 
			mxx = max(mxx , tx[i]);
			mxy = max(mxy , ty[i]);
 
			if((mxx - mnx + 1) * (mxy - mny + 1) == i + 1)
				SUM++ , is[i] = 1;
			else
				is[i] = 0;
 
			mxxt[i] = mxx , mnxt[i] = mnx;
			mxyt[i] = mxy , mnyt[i] = mny;
		}
 
		return SUM;
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 14 ms 21120 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21028 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21276 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 21084 KB Output is correct
12 Correct 14 ms 21104 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 14 ms 21120 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21028 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21276 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 21084 KB Output is correct
12 Correct 14 ms 21104 KB Output is correct
13 Correct 50 ms 21400 KB Output is correct
14 Correct 53 ms 21404 KB Output is correct
15 Correct 28 ms 21340 KB Output is correct
16 Correct 50 ms 21592 KB Output is correct
17 Correct 51 ms 21376 KB Output is correct
18 Correct 50 ms 21336 KB Output is correct
19 Correct 51 ms 21400 KB Output is correct
20 Correct 62 ms 21404 KB Output is correct
21 Correct 28 ms 21340 KB Output is correct
22 Correct 51 ms 21400 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4046 ms 85636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 21340 KB Output is correct
2 Correct 86 ms 27992 KB Output is correct
3 Correct 258 ms 90060 KB Output is correct
4 Correct 253 ms 85464 KB Output is correct
5 Correct 587 ms 98888 KB Output is correct
6 Correct 244 ms 85592 KB Output is correct
7 Correct 380 ms 98900 KB Output is correct
8 Correct 253 ms 93788 KB Output is correct
9 Correct 247 ms 95828 KB Output is correct
10 Correct 245 ms 89684 KB Output is correct
11 Correct 245 ms 88504 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 22736 KB Output is correct
2 Correct 55 ms 22480 KB Output is correct
3 Correct 113 ms 22480 KB Output is correct
4 Correct 165 ms 22544 KB Output is correct
5 Correct 219 ms 22992 KB Output is correct
6 Correct 910 ms 99664 KB Output is correct
7 Correct 924 ms 96848 KB Output is correct
8 Correct 890 ms 99920 KB Output is correct
9 Correct 965 ms 96840 KB Output is correct
10 Correct 856 ms 99672 KB Output is correct
11 Correct 861 ms 99780 KB Output is correct
12 Correct 856 ms 99620 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 14 ms 21120 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21028 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21276 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 21084 KB Output is correct
12 Correct 14 ms 21104 KB Output is correct
13 Correct 50 ms 21400 KB Output is correct
14 Correct 53 ms 21404 KB Output is correct
15 Correct 28 ms 21340 KB Output is correct
16 Correct 50 ms 21592 KB Output is correct
17 Correct 51 ms 21376 KB Output is correct
18 Correct 50 ms 21336 KB Output is correct
19 Correct 51 ms 21400 KB Output is correct
20 Correct 62 ms 21404 KB Output is correct
21 Correct 28 ms 21340 KB Output is correct
22 Correct 51 ms 21400 KB Output is correct
23 Execution timed out 4046 ms 85636 KB Time limit exceeded
24 Halted 0 ms 0 KB -