oj.uz

Submission #831494

# Submission time Handle Problem Language Result Execution time Memory
831494 2023-08-20T09:49:38 Z tolbi Seats (IOI18_seats) C++17
5 / 100
 4000 ms 27720 KB 
#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
struct BIT{
	BIT(){}
	vector<vector<int>> arr;
	void init(int n, int m){
		arr.resize(n,vector<int>(m,0));
	}
	void update(int x, int y, int val){
		arr[x][y]=val;
	}
	int minq(int xl, int xr, int yl, int yr){
		int rval = 23232323;
		for (int i = xl; i <= xr; i++){
			for (int j = yl; j <= yr; j++){
				rval=min(rval,arr[i][j]);
			}
		}
		return rval;
	}
	int maxq(int xl, int xr, int yl, int yr){
		int rval = 0;
		for (int i = xl; i <= xr; i++){
			for (int j = yl; j <= yr; j++){
				rval=max(rval,arr[i][j]);
			}
		}
		return rval;
	}
};
vector<int> R,C;
BIT fenwik;
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;
	fenwik.init(H,W);
	for (int i = 0; i < R.size(); ++i)
	{
		fenwik.update(R[i],C[i],i);
	}
}
int swap_seats(int a, int b) {
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	fenwik.update(R[a],C[a],a);
	fenwik.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,fenwik.minq(0,xl-1,0,W-1));
		if (xr+1<H) minel=min(minel,fenwik.minq(xr+1,H-1,0,W-1));
		if (yl>0) minel=min(minel,fenwik.minq(xl,xr,0,yl-1));
		if (yr+1<W) minel=min(minel,fenwik.minq(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=fenwik.maxq(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:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < R.size(); ++i)
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 49 ms 376 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 9 ms 372 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 23 ms 360 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 49 ms 376 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 9 ms 372 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 23 ms 360 KB Output is correct
13 Correct 744 ms 596 KB Output is correct
14 Correct 639 ms 596 KB Output is correct
15 Correct 746 ms 632 KB Output is correct
16 Execution timed out 4056 ms 1108 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 4050 ms 27720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 596 KB Output is correct
2 Execution timed out 4041 ms 4028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1360 KB Output is correct
2 Correct 20 ms 1248 KB Output is correct
3 Correct 234 ms 1316 KB Output is correct
4 Execution timed out 4048 ms 828 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 49 ms 376 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 8 ms 340 KB Output is correct
9 Correct 9 ms 372 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 23 ms 360 KB Output is correct
13 Correct 744 ms 596 KB Output is correct
14 Correct 639 ms 596 KB Output is correct
15 Correct 746 ms 632 KB Output is correct
16 Execution timed out 4056 ms 1108 KB Time limit exceeded
17 Halted 0 ms 0 KB -