oj.uz

Submission #831528

# Submission time Handle Problem Language Result Execution time Memory
831528 2023-08-20T10:11:35 Z caganyanmaz Seats (IOI18_seats) C++17
5 / 100
 4000 ms 55904 KB 
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

constexpr static int MXN = 1e6;
constexpr static int INF = 1e6;
constexpr static int MXST = MXN<<1;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

struct SegTree
{
	int def;
	function<int(int, int)> merge;
	int n;
	int v[MXST];
	void build(int n, vector<int>& a, function<int(int, int)> merge, int def)
	{
		this->n = n;
		this->merge = merge;
		this->def = def;
		for (int i = n; i < 2*n; i++) v[i] = a[i-n];
		for (int i = n-1; i > 0; i--) v[i] = merge(v[i<<1], v[(i<<1)|1]);
	}
	void set(int i, int val) { for (v[i+=n]=val;i>1;i>>=1) v[i>>1] = merge(v[i], v[i^1]); }
	int get(int l, int r)
	{
		int res = def;
		l = max(l, 0);
		r = min(r, n);
		for (l+=n,r+=n;r>l;r>>=1,l>>=1)
		{
			if (l&1) res = merge(res, v[l++]);
			if (r&1) res = merge(res, v[--r]);
		}
		return res;
	}

};

vector<int> r, c;
SegTree mnr, mxr, mnc, mxc;

int h, w, n;
int counter;
set<int> rects;
int mn(int a, int b) {return min(a,b);}
int mx(int a, int b) {return max(a,b);}

bool is_rect(int i)
{
	int rect_size = (mxr.get(0, i+1) - mnr.get(0, i+1) + 1) * (mxc.get(0, i+1) - mnc.get(0, i+1) + 1);
	return rect_size == i+1;
}

void create_table()
{
	counter = 0;
	mnr.build(n, r, mn, INF);
	mxr.build(n, r, mx, -INF);
	mnc.build(n, c, mn, INF);
	mxc.build(n, c, mx, -INF);
	for (int i = 0; i < n; i++)
		if (is_rect(i))
			rects.insert(i);
	debug(rects);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) 
{
	r = R, c = C;
	h = H, w = W;
	n = h*w;
	set<int> rects;
	create_table();
}

int swap_seats(int a, int b)
{
	if (a > b)
		swap(a, b);
	for (int i= 0; i < 2; i++)
	{
		mnr.set(a, r[b]);
		mxr.set(a, r[b]);
		mnc.set(a, c[b]);
		mxc.set(a, c[b]);
		swap(a, b);
	}
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for (int i = a; i <= b; i++)
	{
		bool res = is_rect(i);
		if (!res)
			rects.erase(i);
		if (res)
			rects.insert(i);
	}
	return rects.size();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 8 ms 464 KB Output is correct
3 Correct 21 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct
5 Correct 36 ms 456 KB Output is correct
6 Correct 21 ms 460 KB Output is correct
7 Correct 22 ms 464 KB Output is correct
8 Correct 21 ms 468 KB Output is correct
9 Correct 22 ms 468 KB Output is correct
10 Correct 23 ms 464 KB Output is correct
11 Correct 24 ms 460 KB Output is correct
12 Correct 32 ms 440 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 8 ms 464 KB Output is correct
3 Correct 21 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct
5 Correct 36 ms 456 KB Output is correct
6 Correct 21 ms 460 KB Output is correct
7 Correct 22 ms 464 KB Output is correct
8 Correct 21 ms 468 KB Output is correct
9 Correct 22 ms 468 KB Output is correct
10 Correct 23 ms 464 KB Output is correct
11 Correct 24 ms 460 KB Output is correct
12 Correct 32 ms 440 KB Output is correct
13 Execution timed out 4056 ms 984 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4077 ms 55904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 1116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1720 KB Output is correct
2 Correct 30 ms 1612 KB Output is correct
3 Correct 326 ms 1556 KB Output is correct
4 Execution timed out 4066 ms 1432 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 8 ms 464 KB Output is correct
3 Correct 21 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct
5 Correct 36 ms 456 KB Output is correct
6 Correct 21 ms 460 KB Output is correct
7 Correct 22 ms 464 KB Output is correct
8 Correct 21 ms 468 KB Output is correct
9 Correct 22 ms 468 KB Output is correct
10 Correct 23 ms 464 KB Output is correct
11 Correct 24 ms 460 KB Output is correct
12 Correct 32 ms 440 KB Output is correct
13 Execution timed out 4056 ms 984 KB Time limit exceeded
14 Halted 0 ms 0 KB -