#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
std::vector<int> r, c;
vector<int>aux;
ll h, w, hw;
bool acum[1000002];
int ans;
void updetiar(int dd, int ht);
struct segTree{
int dd, ht, mid;
int val;
bool isMax;
segTree *L, *R;
segTree(int l, int rr, bool maximos){
dd = l;
ht = rr;
mid = (dd + ht)/2;
val = 0;
isMax = maximos;
if(l != rr){
L = new segTree(l, mid, maximos);
R = new segTree(mid+1, ht, maximos);
if(isMax and L->val > R->val)val = L->val;
else if(isMax)val = R->val;
else if(L->val < R->val)val = L->val;
else val = R->val;
}else{
val = aux[l];
}
}
void update(){
if(isMax and L->val > R->val)val = L->val;
else if(isMax)val = R->val;
else if(L->val < R->val)val = L->val;
else val = R->val;
}
void cambiar(int pos, int cuanto){
if(dd == ht)val = cuanto;
else{
if(pos <= mid)L->cambiar(pos, cuanto);
else R->cambiar(pos, cuanto);
update();
}
}
int query(int l, int rr){
if(dd == l and rr == ht)return val;
if( rr<= mid)return L->query(l, rr);
if(mid < l)return R->query(l, rr);
if(isMax){
return max(L->query(l, mid), R->query(mid+1, rr));
}else return min(L->query(l, mid), R->query(mid+1, rr));
}
};
//segTree *maxH, *minH, *maxC, *minC;
vector<int>maxH, minH, maxC, minC;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h = H;
w = W;
hw = h*w;
for(int i = 0 ; i < hw ; i ++)aux.pb(R[i]);
//maxH = new segTree(0, hw-1, true);
//minH = new segTree(0, hw-1, false);
for(int i = 0 ; i < hw ; i ++)aux[i] = C[i];
//maxC = new segTree(0, hw-1, true);
//minC = new segTree(0, hw-1, false);
for(int i = 0 ; i <= hw ; i ++)acum[i] = false;
int mxH, mxC, mnH, mnC;
for(int i = 0 ; i < hw ; i ++){
mxH = max(R[i], mxH);
mxC = max(C[i], mxC);
mnH = min(R[i], mnH);
mnC = min(C[i], mnC);
maxH.pb(mxH);
maxC.pb(mxC);
minH.pb(mnH);
minC.pb(mnC);
}
ans = 0;
updetiar(0, hw-1);
}
void updetiar(int dd, int ht){
ll alto, ancho;
//cout << " c " << dd << " " << ht << endl;
//int minimoH = minH->query(0, dd), minimoC = minC->query(0, dd), maximoH = maxH->query(0, dd), maximoC = maxC->query(0, dd), nextI;
int minimoH ,minimoC , maximoH, maximoC, nextI;
if(dd != 0){
minimoH = minH[dd-1], minimoC = minC[dd-1], maximoH = maxH[dd-1], maximoC = maxC[dd-1];
nextI = dd;
minimoH = min(minimoH, r[nextI]);
minimoC = min(minimoC, c[nextI]);
maximoH = max(maximoH, r[nextI]);
maximoC = max(maximoC, c[nextI]);
minH[nextI] = minimoH;
maxH[nextI] = maximoH;
minC[nextI] = minimoC;
maxC[nextI] = maximoC;
}else{
minimoH = r[0];
minimoC = c[0];
maximoH = r[0];
maximoC = c[0];
minH[0] = minimoH;
maxH[0] = maximoH;
minC[0] = minimoC;
maxC[0] = maximoC;
}
for(int i = dd ; i <= ht ;){
//cout << i << endl;
//alto = maxH->query(0, i) - minH->query(0, i) + 1;
//ancho = maxC->query(0, i) - minC->query(0, i) + 1;
alto = maximoH - minimoH + 1;
ancho = maximoC - minimoC + 1;
nextI = i+1;
bool flag = false;
if(ancho * alto == i + 1){
//ans ++ ;
flag = true;
//nextI = i + min(ancho, alto);
//cout << i << endl;
}else{
//nextI = ancho*alto-1;
}
if(nextI <= ht){
minimoH = min(minimoH, r[nextI]);
minimoC = min(minimoC, c[nextI]);
maximoH = max(maximoH, r[nextI]);
maximoC = max(maximoC, c[nextI]);
minH[nextI] = minimoH;
maxH[nextI] = maximoH;
minC[nextI] = minimoC;
maxC[nextI] = maximoC;
}
if(acum[i] and !flag){
ans -- ;
//cout << "se perdio " << i << endl;
}else if(!acum[i] and flag){
ans ++ ;
}
acum[i] = flag;
i = nextI;
}
}
int swap_seats(int a, int b) {
if(a > b)swap(a, b);
/*
maxH->cambiar(a, r[b]);
minH->cambiar(a, r[b]);
maxH->cambiar(b, r[a]);
minH->cambiar(b, r[a]);
maxC->cambiar(a, c[b]);
minC->cambiar(a, c[b]);
maxC->cambiar(b, c[a]);
minC->cambiar(b, c[a]);
* */
swap(r[a], r[b]);
swap(c[a], c[b]);
updetiar(a, b);
//cout << endl;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
57 ms |
924 KB |
Output is correct |
14 |
Correct |
54 ms |
912 KB |
Output is correct |
15 |
Correct |
53 ms |
916 KB |
Output is correct |
16 |
Correct |
54 ms |
852 KB |
Output is correct |
17 |
Correct |
53 ms |
852 KB |
Output is correct |
18 |
Correct |
53 ms |
916 KB |
Output is correct |
19 |
Correct |
58 ms |
928 KB |
Output is correct |
20 |
Correct |
54 ms |
916 KB |
Output is correct |
21 |
Correct |
54 ms |
972 KB |
Output is correct |
22 |
Correct |
54 ms |
936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4016 ms |
49992 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
852 KB |
Output is correct |
2 |
Correct |
92 ms |
5216 KB |
Output is correct |
3 |
Correct |
261 ms |
64540 KB |
Output is correct |
4 |
Correct |
272 ms |
64744 KB |
Output is correct |
5 |
Correct |
261 ms |
64808 KB |
Output is correct |
6 |
Correct |
280 ms |
64820 KB |
Output is correct |
7 |
Correct |
262 ms |
64700 KB |
Output is correct |
8 |
Correct |
261 ms |
64812 KB |
Output is correct |
9 |
Correct |
293 ms |
64712 KB |
Output is correct |
10 |
Correct |
271 ms |
64688 KB |
Output is correct |
11 |
Correct |
278 ms |
64800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1360 KB |
Output is correct |
2 |
Correct |
13 ms |
1360 KB |
Output is correct |
3 |
Correct |
17 ms |
1360 KB |
Output is correct |
4 |
Correct |
63 ms |
1348 KB |
Output is correct |
5 |
Correct |
517 ms |
1688 KB |
Output is correct |
6 |
Execution timed out |
4059 ms |
50388 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
57 ms |
924 KB |
Output is correct |
14 |
Correct |
54 ms |
912 KB |
Output is correct |
15 |
Correct |
53 ms |
916 KB |
Output is correct |
16 |
Correct |
54 ms |
852 KB |
Output is correct |
17 |
Correct |
53 ms |
852 KB |
Output is correct |
18 |
Correct |
53 ms |
916 KB |
Output is correct |
19 |
Correct |
58 ms |
928 KB |
Output is correct |
20 |
Correct |
54 ms |
916 KB |
Output is correct |
21 |
Correct |
54 ms |
972 KB |
Output is correct |
22 |
Correct |
54 ms |
936 KB |
Output is correct |
23 |
Execution timed out |
4016 ms |
49992 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |