oj.uz

답안 #831564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831564 2023-08-20T10:25:34 Z tolbi 자리 배치 (IOI18_seats) C++17
5 / 100
 4000 ms 72796 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].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,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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 10 ms 388 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 54 ms 420 KB Output is correct
6 Correct 10 ms 492 KB Output is correct
7 Correct 12 ms 404 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 11 ms 392 KB Output is correct
10 Correct 10 ms 412 KB Output is correct
11 Correct 9 ms 360 KB Output is correct
12 Correct 17 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 10 ms 388 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 54 ms 420 KB Output is correct
6 Correct 10 ms 492 KB Output is correct
7 Correct 12 ms 404 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 11 ms 392 KB Output is correct
10 Correct 10 ms 412 KB Output is correct
11 Correct 9 ms 360 KB Output is correct
12 Correct 17 ms 340 KB Output is correct
13 Correct 78 ms 1084 KB Output is correct
14 Correct 92 ms 1076 KB Output is correct
15 Correct 36 ms 948 KB Output is correct
16 Execution timed out 4062 ms 4052 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2778 ms 56812 KB Output is correct
2 Correct 2120 ms 72796 KB Output is correct
3 Execution timed out 4073 ms 72788 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 1080 KB Output is correct
2 Correct 767 ms 10732 KB Output is correct
3 Execution timed out 4034 ms 56800 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1360 KB Output is correct
2 Correct 25 ms 1332 KB Output is correct
3 Correct 176 ms 1228 KB Output is correct
4 Correct 1787 ms 1332 KB Output is correct
5 Correct 274 ms 1796 KB Output is correct
6 Correct 1540 ms 48692 KB Output is correct
7 Correct 1667 ms 48800 KB Output is correct
8 Correct 2353 ms 48808 KB Output is correct
9 Correct 1045 ms 48808 KB Output is correct
10 Execution timed out 4035 ms 48804 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 10 ms 388 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 54 ms 420 KB Output is correct
6 Correct 10 ms 492 KB Output is correct
7 Correct 12 ms 404 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 11 ms 392 KB Output is correct
10 Correct 10 ms 412 KB Output is correct
11 Correct 9 ms 360 KB Output is correct
12 Correct 17 ms 340 KB Output is correct
13 Correct 78 ms 1084 KB Output is correct
14 Correct 92 ms 1076 KB Output is correct
15 Correct 36 ms 948 KB Output is correct
16 Execution timed out 4062 ms 4052 KB Time limit exceeded
17 Halted 0 ms 0 KB -