oj.uz

답안 #77378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77378 2018-09-27T02:36:42 Z Just_Solve_The_Problem 자리 배치 (IOI18_seats) C++11
0 / 100
 569 ms 56796 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 {
  		ans++;
  		i = area;
  	}
  }                     
	return ans; 
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 569 ms 56796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 56796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 56796 KB Output is correct
2 Incorrect 37 ms 56796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -