| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 831466 |
2023-08-20T09:27:42 Z |
tolbi |
Seats (IOI18_seats) |
C++17 |
|
4000 ms |
32092 KB |
#include <bits/stdc++.h>
using namespace std;
#include "seats.h"
#define tol(bi) (1LL<<((int)(bi)))
struct BIT{
vector<int> arr;
BIT(int n){
arr.resize(n,0);
}
void update(int x, int val){
arr[x]=val;
}
int maxq(int l, int r){
int rval = 0;
for (int i = l; i <= r; i++){
rval=max(rval,arr[i]);
}
return rval;
}
int minq(int l, int r){
int rval = 23232323;
for (int i = l ;i <= r; i++){
rval=min(rval,arr[i]);
}
return rval;
}
};
vector<int> R,C;
vector<BIT> horizontal;
vector<BIT> vertical;
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
R=_R,C=_C;
horizontal.resize(W,H);
vertical.resize(H,W);
for (int i = 0; i < R.size(); ++i)
{
vertical[R[i]].update(C[i],i);
horizontal[C[i]].update(R[i],i);
}
}
int swap_seats(int a, int b) {
swap(R[a],R[b]);
swap(C[a],C[b]);
vertical[R[a]].update(C[a],a);
vertical[R[b]].update(C[b],b);
horizontal[C[a]].update(R[a],a);
horizontal[C[b]].update(R[b],b);
int n = R.size();
int crmax = 0;
int ans = 1;
int xl=R[0],xr=R[0];
int yl=C[0],yr=C[0];
while (crmax<R.size()-1){
int sec1=n, sec2=n, sec3=n, sec4=n;
if (yl>0){
sec1=horizontal[yl-1].minq(xl,xr);
}
if (yr<horizontal.size()-1){
sec2=horizontal[yr+1].minq(xl,xr);
}
if (xl>0){
sec3=vertical[xl-1].minq(yl,yr);
}
if (xr<vertical.size()-1){
sec4=vertical[xr+1].minq(yl,yr);
}
int minel = n;
minel=min(minel,sec1);
minel=min(minel,sec2);
minel=min(minel,sec3);
minel=min(minel,sec4);
if (minel==sec1) minel=horizontal[yl-1].maxq(xl,xr);
if (minel==sec2) minel=horizontal[yr+1].maxq(xl,xr);
if (minel==sec3) minel=vertical[xl-1].maxq(yl,yr);
if (minel==sec4) minel=vertical[xr+1].maxq(yl,yr);
xr=max(xr,R[minel]);
xl=min(xl,R[minel]);
yr=max(yr,C[minel]);
yl=min(yl,C[minel]);
crmax=max(crmax,minel);
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:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < R.size(); ++i)
| ~~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while (crmax<R.size()-1){
| ~~~~~^~~~~~~~~~~
seats.cpp:59:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (yr<horizontal.size()-1){
| ~~^~~~~~~~~~~~~~~~~~~~
seats.cpp:65:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BIT>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (xr<vertical.size()-1){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
32092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
