oj.uz

답안 #77377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77377 2018-09-27T02:35:10 Z Just_Solve_The_Problem 자리 배치 (IOI18_seats) C++11
5 / 100
 4000 ms 57248 KB 
#include <bits/stdc++.h>
#include "seats.h"
// #include "grader.cpp"

#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define OK puts("ok");

using namespace std;

const int N = (int)1e6 + 7;
const int inf = (int)1e9 + 7;

int n;

struct T {
	int tree[2][4 * N];
	T () {		
	}
	void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			tree[0][v] = tree[1][v] = val;
			return ;
		}
		int mid = (tl + tr) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, tl, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, tr);
		}
		tree[0][v] = min(tree[0][v + v], tree[0][v + v + 1]);
		tree[1][v] = max(tree[1][v + v], tree[1][v + v + 1]);
	}
	int get(int l, int r, int tp, int v = 1, int tl = 1, int tr = n) {
		if (tl > r || tr < l) return ((tp == 0) ? inf : 0);
		if (l <= tl && tr <= r) return tree[tp][v];
		int mid = (tl + tr) >> 1;
		int temp;
		if (tp == 0) temp = min(get(l, r, tp, v + v, tl, mid), get(l, r, tp, v + v + 1, mid + 1, tr));
		else temp = max(get(l, r, tp, v + v, tl, mid), get(l, r, tp, v + v + 1, mid + 1, tr));
		return temp;
	}
};
T tr[2];

int h, w;
int ans;
int r[N], c[N];

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  h = H;
  w = W;
  n = h * w;
  for (int i = 1; i <= n; i++) {
  	tr[0].upd(i, R[i - 1]);
  	tr[1].upd(i, C[i - 1]);
  	r[i] = R[i - 1];
  	c[i] = C[i - 1];
  }
}

int swap_seats(int a, int b) {
	a++; b++;
  tr[0].upd(a, r[b]);
  tr[0].upd(b, r[a]);
  swap(r[a], r[b]);
  tr[1].upd(a, c[b]);
  tr[1].upd(b, c[a]);
  swap(c[a], c[b]);
  ans = 0;
  for (int i = 1; i <= n; i++) {
  	int area = (tr[0].get(1, i, 1) - tr[0].get(1, i, 0) + 1) * (tr[1].get(1, i, 1) - tr[1].get(1, i, 0) + 1);
  	if (i == area) {
  		ans++;
  	} else {
  		i = area - 1;
  	}
  }                     
	return ans; 
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 10 ms 628 KB Output is correct
3 Correct 13 ms 628 KB Output is correct
4 Correct 9 ms 652 KB Output is correct
5 Correct 52 ms 668 KB Output is correct
6 Correct 8 ms 744 KB Output is correct
7 Correct 8 ms 780 KB Output is correct
8 Correct 15 ms 800 KB Output is correct
9 Correct 15 ms 804 KB Output is correct
10 Correct 12 ms 804 KB Output is correct
11 Correct 8 ms 804 KB Output is correct
12 Correct 54 ms 824 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 10 ms 628 KB Output is correct
3 Correct 13 ms 628 KB Output is correct
4 Correct 9 ms 652 KB Output is correct
5 Correct 52 ms 668 KB Output is correct
6 Correct 8 ms 744 KB Output is correct
7 Correct 8 ms 780 KB Output is correct
8 Correct 15 ms 800 KB Output is correct
9 Correct 15 ms 804 KB Output is correct
10 Correct 12 ms 804 KB Output is correct
11 Correct 8 ms 804 KB Output is correct
12 Correct 54 ms 824 KB Output is correct
13 Correct 25 ms 1440 KB Output is correct
14 Correct 24 ms 1440 KB Output is correct
15 Correct 29 ms 1440 KB Output is correct
16 Execution timed out 4100 ms 1440 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 570 ms 56996 KB Output is correct
2 Correct 649 ms 57120 KB Output is correct
3 Execution timed out 4009 ms 57120 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 57120 KB Output is correct
2 Correct 206 ms 57120 KB Output is correct
3 Execution timed out 4043 ms 57248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 57248 KB Output is correct
2 Correct 39 ms 57248 KB Output is correct
3 Correct 506 ms 57248 KB Output is correct
4 Execution timed out 4035 ms 57248 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 10 ms 628 KB Output is correct
3 Correct 13 ms 628 KB Output is correct
4 Correct 9 ms 652 KB Output is correct
5 Correct 52 ms 668 KB Output is correct
6 Correct 8 ms 744 KB Output is correct
7 Correct 8 ms 780 KB Output is correct
8 Correct 15 ms 800 KB Output is correct
9 Correct 15 ms 804 KB Output is correct
10 Correct 12 ms 804 KB Output is correct
11 Correct 8 ms 804 KB Output is correct
12 Correct 54 ms 824 KB Output is correct
13 Correct 25 ms 1440 KB Output is correct
14 Correct 24 ms 1440 KB Output is correct
15 Correct 29 ms 1440 KB Output is correct
16 Execution timed out 4100 ms 1440 KB Time limit exceeded
17 Halted 0 ms 0 KB -