oj.uz

Submission #77381

# Submission time Handle Problem Language Result Execution time Memory
77381 2018-09-27T04:10:46 Z Just_Solve_The_Problem Seats (IOI18_seats) C++11
5 / 100
 4000 ms 57260 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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 508 KB Output is correct
3 Correct 8 ms 584 KB Output is correct
4 Correct 8 ms 616 KB Output is correct
5 Correct 61 ms 616 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 15 ms 616 KB Output is correct
9 Correct 14 ms 616 KB Output is correct
10 Correct 8 ms 696 KB Output is correct
11 Correct 8 ms 792 KB Output is correct
12 Correct 58 ms 804 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 508 KB Output is correct
3 Correct 8 ms 584 KB Output is correct
4 Correct 8 ms 616 KB Output is correct
5 Correct 61 ms 616 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 15 ms 616 KB Output is correct
9 Correct 14 ms 616 KB Output is correct
10 Correct 8 ms 696 KB Output is correct
11 Correct 8 ms 792 KB Output is correct
12 Correct 58 ms 804 KB Output is correct
13 Correct 24 ms 1488 KB Output is correct
14 Correct 19 ms 1488 KB Output is correct
15 Correct 17 ms 1488 KB Output is correct
16 Execution timed out 4018 ms 1488 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 57260 KB Output is correct
2 Correct 626 ms 57260 KB Output is correct
3 Execution timed out 4073 ms 57260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 57260 KB Output is correct
2 Correct 204 ms 57260 KB Output is correct
3 Execution timed out 4038 ms 57260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57260 KB Output is correct
2 Correct 65 ms 57260 KB Output is correct
3 Correct 514 ms 57260 KB Output is correct
4 Execution timed out 4075 ms 57260 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 508 KB Output is correct
3 Correct 8 ms 584 KB Output is correct
4 Correct 8 ms 616 KB Output is correct
5 Correct 61 ms 616 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 8 ms 616 KB Output is correct
8 Correct 15 ms 616 KB Output is correct
9 Correct 14 ms 616 KB Output is correct
10 Correct 8 ms 696 KB Output is correct
11 Correct 8 ms 792 KB Output is correct
12 Correct 58 ms 804 KB Output is correct
13 Correct 24 ms 1488 KB Output is correct
14 Correct 19 ms 1488 KB Output is correct
15 Correct 17 ms 1488 KB Output is correct
16 Execution timed out 4018 ms 1488 KB Time limit exceeded
17 Halted 0 ms 0 KB -