Submission #106600

#	Time	Username	Problem	Language	Result	Execution time	Memory
106600		Just_Solve_The_Problem	Seats (IOI18_seats)	C++11	0 / 100	4070 ms	93216 KiB

seats

#include <stdio.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;

inline int min(const int &a, const int &b) {
	return (a < b) ? a : b;
}

inline int max(const int &a, const int &b) {
	return (a < b) ? b : a;
}

struct T {
	int tree[2 * N][2];
	T () {		
	}
	void build(int v, int l, int r, vector <int> &V) {
		if (l == r) {
			tree[v][0] = tree[v][1] = V[l - 1];
			return ;
		}
		int mid = (l + r) >> 1;
		build(v + v, l, mid, V);
		build(v + v + 1, mid + 1, r, V);
		tree[v][0] = min(tree[v + v][0], tree[v + v + 1][0]);
		tree[v][1] = max(tree[v + v][1], tree[v + v + 1][1]);
	} 
	void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			tree[v][0] = tree[v][1] = 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[v][0] = min(tree[v + v][0], tree[v + v + 1][0]);
		tree[v][1] = max(tree[v + v][1], tree[v + v + 1][1]);
	}
	pair < int, int > get(int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (tl > r || tr < l) return make_pair(inf, 0);
		if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
		int mid = (tl + tr) >> 1;
		pair < int, int > tp1, tp2;
		tp1 = get(l, r, v + v, tl, mid);
		tp2 = get(l, r, v + v + 1, mid + 1, tr);
		return make_pair(min(tp1.first, tp2.first), max(tp1.second, tp2.second));
	}
};
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;
  tr[0].build(1, 1, n, R);
  tr[1].build(1, 1, n, C);
  for (int i = 0; i < n; i++) {
		c[i + 1] = C[i];
		r[i + 1] = R[i];
  }
}

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

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^
seats.cpp:57:53: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                            ~~~~~~~~~^
seats.cpp:57:65: warning: array subscript is above array bounds [-Warray-bounds]
   if (l <= tl && tr <= r) return make_pair(tree[0][v], tree[1][v]);
                                                        ~~~~~~~~~^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30