oj.uz

Submission #831562

# Submission time Handle Problem Language Result Execution time Memory
831562 2023-08-20T10:25:09 Z tolbi Seats (IOI18_seats) C++17
5 / 100
 4000 ms 65468 KB 
#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
const int LIMN=1e9;
const int LIMM=1e9;
vector<int> R,C;
struct SegTree2DMax{
	struct SegTreeMax{
		vector<int> segtree;
		SegTreeMax(int n){
			segtree.resize(tol(ceil(log2(n)+1))-1,23232323);
		}
		void update(int node, int val){
			node+=segtree.size()/2;
			segtree[node]=val;
			while (node){
				node=(node-1)/2;
				segtree[node]=max(segtree[node*2+1],segtree[node*2+2]);
			}
		}
		int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
			if (r==-1) r = segtree.size()/2;
			if (l>=tarl && r<=tarr) return segtree[node];
			if (l>tarr || r<tarl) return 0;
			int mid = l+(r-l)/2;
			int lnode = query(tarl, tarr, l, mid, node*2+1);
			int rnode = query(tarl, tarr, mid+1, r, node*2+2);
			return max(lnode, rnode);
		}
	};
	vector<SegTreeMax> segtree;
	SegTree2DMax(){}
	void init(int n, int m){
		segtree.resize(tol(ceil(log2(n)+1))-1,m);
	}
	void update(int node, int x, int val){
		node+=segtree.size()/2;
		segtree[node].update(x,val);
		while (node){
			node=(node-1)/2;
			int lnode = segtree[node*2+1].segtree[x+segtree[node*2+1].segtree.size()/2];
			int rnode = segtree[node*2+2].segtree[x+segtree[node*2+2].segtree.size()/2];
			segtree[node].update(x,max(lnode, rnode));
		}
	}
	int query(int tarl, int tarr, int xl, int xr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node].query(xl,xr);
		if (l>tarr || r<tarl) return 0;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, xl, xr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, xl, xr, mid+1, r, node*2+2);
		return max(lnode, rnode);
	}
};
struct SegTree2DMin{
	struct SegTreeMin{
		vector<int> segtree;
		SegTreeMin(int n){
			segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
		}
		void update(int node, int val){
			node+=segtree.size()/2;
			segtree[node]=val;
			while (node){
				node=(node-1)/2;
				segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
			}
		}
		int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
			if (r==-1) r = segtree.size()/2;
			if (l>=tarl && r<=tarr) return segtree[node];
			if (l>tarr || r<tarl) return 23232323;
			int mid = l+(r-l)/2;
			int lnode = query(tarl, tarr, l, mid, node*2+1);
			int rnode = query(tarl, tarr, mid+1, r, node*2+2);
			return min(lnode, rnode);
		}
	};
	vector<SegTreeMin> segtree;
	SegTree2DMin(){}
	void init(int n, int m){
		segtree.resize(tol(ceil(log2(n)+1))-1,m);
	}
	void update(int node, int x, int val){
		node+=segtree.size()/2;
		segtree[node].update(x,val);
		while (node){
			node=(node-1)/2;
			int lnode = segtree[node*2+1].query(x,x);
			int rnode = segtree[node*2+2].query(x,x);
			segtree[node].update(x,min(lnode, rnode));
		}
	}
	int query(int tarl, int tarr, int xl, int xr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tarl && r<=tarr) return segtree[node].query(xl,xr);
		if (l>tarr || r<tarl) return 23232323;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, xl, xr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, xl, xr, mid+1, r, node*2+2);
		return min(lnode, rnode);
	}
};
SegTree2DMin segtreemin;
SegTree2DMax segtreemax;
int H,W;
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) {
	R=_R,C=_C;
	H=_H,W=_W;
	segtreemin.init(H,W);
	segtreemax.init(H,W);
	for (int i = 0; i < R.size(); ++i)
	{
		segtreemin.update(R[i],C[i],i);
		segtreemax.update(R[i],C[i],i);
	}
}
int swap_seats(int a, int b) {
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	segtreemin.update(R[a],C[a],a);
	segtreemax.update(R[a],C[a],a);
	segtreemin.update(R[b],C[b],b);
	segtreemax.update(R[b],C[b],b);
	int crmax = 0;
	int ans = 1;
	int xl=R[0],xr=R[0];
	int yl=C[0],yr=C[0];
	while (xl>0 || xr<H-1 || yl>0 || yr<W-1){
		int minel = 23232323;
		if (xl>0) minel=min(minel,segtreemin.query(0,xl-1,0,W-1));
		if (xr+1<H) minel=min(minel,segtreemin.query(xr+1,H-1,0,W-1));
		if (yl>0) minel=min(minel,segtreemin.query(xl,xr,0,yl-1));
		if (yr+1<W) minel=min(minel,segtreemin.query(xl,xr,yr+1,W-1));
		xr=max(xr,R[minel]);
		xl=min(xl,R[minel]);
		yr=max(yr,C[minel]);
		yl=min(yl,C[minel]);
		crmax=segtreemax.query(xl,xr,yl,yr);
		if ((xr-xl+1)*(yr-yl+1)==crmax+1) ans++;
	}
	return ans;
}

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for (int i = 0; i < R.size(); ++i)
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 16 ms 376 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 57 ms 380 KB Output is correct
6 Correct 9 ms 352 KB Output is correct
7 Correct 14 ms 372 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 15 ms 412 KB Output is correct
11 Correct 9 ms 380 KB Output is correct
12 Correct 20 ms 484 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 16 ms 376 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 57 ms 380 KB Output is correct
6 Correct 9 ms 352 KB Output is correct
7 Correct 14 ms 372 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 15 ms 412 KB Output is correct
11 Correct 9 ms 380 KB Output is correct
12 Correct 20 ms 484 KB Output is correct
13 Correct 78 ms 1092 KB Output is correct
14 Correct 85 ms 1280 KB Output is correct
15 Correct 32 ms 1144 KB Output is correct
16 Execution timed out 4045 ms 4308 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1084 KB Output is correct
2 Correct 962 ms 10984 KB Output is correct
3 Execution timed out 4010 ms 64088 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1380 KB Output is correct
2 Correct 28 ms 1280 KB Output is correct
3 Correct 207 ms 1240 KB Output is correct
4 Correct 1875 ms 1280 KB Output is correct
5 Correct 306 ms 2532 KB Output is correct
6 Correct 1895 ms 49252 KB Output is correct
7 Correct 1742 ms 65340 KB Output is correct
8 Correct 2773 ms 65468 KB Output is correct
9 Correct 1180 ms 65408 KB Output is correct
10 Execution timed out 4072 ms 65400 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 16 ms 376 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 57 ms 380 KB Output is correct
6 Correct 9 ms 352 KB Output is correct
7 Correct 14 ms 372 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 15 ms 412 KB Output is correct
11 Correct 9 ms 380 KB Output is correct
12 Correct 20 ms 484 KB Output is correct
13 Correct 78 ms 1092 KB Output is correct
14 Correct 85 ms 1280 KB Output is correct
15 Correct 32 ms 1144 KB Output is correct
16 Execution timed out 4045 ms 4308 KB Time limit exceeded
17 Halted 0 ms 0 KB -