#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> g;int h,w;int n;
pair<ll,ll> cmi[1000001];pair<ll,ll> cmx[1000001];
int cl[1000001],cr[1000001],cu[1000001],cd[1000001];
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
void add(int idx, int val) {
for (++idx; idx < n; idx += idx & -idx)
bit[idx] += val;
}
void range_add(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
int point_query(int idx) {
int ret = 0;
for (++idx; idx > 0; idx -= idx & -idx)
ret += bit[idx];
return ret;
}
};
FenwickTree tf(1000010);
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;w=W;n=h*w;for(int i=0;i<n;i++){g.push_back({R[i],C[i]});}
//tf=FenwickTree(1000001);
/*tf.range_add(0,1000,5);
tf.range_add(5,1000,5);
cerr<<tf.point_query(2)<<' '<<tf.point_query(8)<<endl;*/
//exit(1);
pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
long long t=0;
for(int i=0;i<=n;i++){
mi=min(mi,g[i]);mx=max(mx,g[i]);
if(g[i].second<lm)lm=g[i].second;
if(g[i].second>rm)rm=g[i].second;
if(g[i].first<um)um=g[i].first;
if(g[i].first>dm)dm=g[i].first;
//cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
int c=tf.point_query(i);
tf.add(i,t-c);
}
}
int swap_seats(int a, int b) {
swap(g[a],g[b]);
pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
long long t=0;
if(a>b)swap(a,b);
if(a>0&&b>0){int i=a-1;t=tf.point_query(i);mi=cmi[i];mx=cmx[i];lm=cl[i];rm=cr[i];um=cu[i];dm=cd[i];}
int bb=-1;
for(int i=a;i<=b;i++){
mi=min(mi,g[i]);mx=max(mx,g[i]);
if(g[i].second<lm)lm=g[i].second;
if(g[i].second>rm)rm=g[i].second;
if(g[i].first<um)um=g[i].first;
if(g[i].first>dm)dm=g[i].first;
//cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
int c=tf.point_query(i);
tf.add(i,t-c);
if(i==b)bb=t-c;
//cerr<<lm<<'-'<<um<<'-'<<rm<<'-'<<dm<<endl;
//cerr<<(lm-rm)<<' '<<mx.second-mi.second<<endl;
//cerr<<(lm-rm==mx.second-mi.second)<<' '<<(dm-um==mx.first-mi.first)<<endl;
}
tf.range_add(b+1,n,bb);
return tf.point_query(n-1);
}
/*
2 3 3
0 0
1 0
1 1
0 1
0 2
1 2
1 4
0 5
0 1
*/
/*
0 3 1
4 2 5
5 3 1
4 2 0
5 3 0
4 2 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4308 KB |
Output is correct |
2 |
Correct |
6 ms |
4456 KB |
Output is correct |
3 |
Correct |
10 ms |
4412 KB |
Output is correct |
4 |
Correct |
10 ms |
4380 KB |
Output is correct |
5 |
Correct |
10 ms |
4372 KB |
Output is correct |
6 |
Correct |
10 ms |
4436 KB |
Output is correct |
7 |
Correct |
11 ms |
4436 KB |
Output is correct |
8 |
Correct |
9 ms |
4420 KB |
Output is correct |
9 |
Correct |
9 ms |
4436 KB |
Output is correct |
10 |
Correct |
12 ms |
4436 KB |
Output is correct |
11 |
Correct |
10 ms |
4436 KB |
Output is correct |
12 |
Correct |
10 ms |
4376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4308 KB |
Output is correct |
2 |
Correct |
6 ms |
4456 KB |
Output is correct |
3 |
Correct |
10 ms |
4412 KB |
Output is correct |
4 |
Correct |
10 ms |
4380 KB |
Output is correct |
5 |
Correct |
10 ms |
4372 KB |
Output is correct |
6 |
Correct |
10 ms |
4436 KB |
Output is correct |
7 |
Correct |
11 ms |
4436 KB |
Output is correct |
8 |
Correct |
9 ms |
4420 KB |
Output is correct |
9 |
Correct |
9 ms |
4436 KB |
Output is correct |
10 |
Correct |
12 ms |
4436 KB |
Output is correct |
11 |
Correct |
10 ms |
4436 KB |
Output is correct |
12 |
Correct |
10 ms |
4376 KB |
Output is correct |
13 |
Correct |
497 ms |
5332 KB |
Output is correct |
14 |
Correct |
537 ms |
5336 KB |
Output is correct |
15 |
Correct |
571 ms |
5328 KB |
Output is correct |
16 |
Correct |
514 ms |
5344 KB |
Output is correct |
17 |
Correct |
523 ms |
5328 KB |
Output is correct |
18 |
Correct |
508 ms |
5344 KB |
Output is correct |
19 |
Correct |
508 ms |
5348 KB |
Output is correct |
20 |
Correct |
493 ms |
5328 KB |
Output is correct |
21 |
Correct |
502 ms |
5328 KB |
Output is correct |
22 |
Correct |
502 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4035 ms |
82556 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
772 ms |
5224 KB |
Output is correct |
2 |
Correct |
737 ms |
12076 KB |
Output is correct |
3 |
Correct |
883 ms |
83440 KB |
Output is correct |
4 |
Correct |
888 ms |
83684 KB |
Output is correct |
5 |
Correct |
917 ms |
83532 KB |
Output is correct |
6 |
Correct |
862 ms |
83640 KB |
Output is correct |
7 |
Correct |
950 ms |
83660 KB |
Output is correct |
8 |
Correct |
859 ms |
83564 KB |
Output is correct |
9 |
Correct |
870 ms |
83668 KB |
Output is correct |
10 |
Correct |
869 ms |
83572 KB |
Output is correct |
11 |
Correct |
930 ms |
83588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
5192 KB |
Output is correct |
2 |
Correct |
27 ms |
5316 KB |
Output is correct |
3 |
Correct |
80 ms |
5296 KB |
Output is correct |
4 |
Correct |
580 ms |
5272 KB |
Output is correct |
5 |
Execution timed out |
4054 ms |
5736 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4308 KB |
Output is correct |
2 |
Correct |
6 ms |
4456 KB |
Output is correct |
3 |
Correct |
10 ms |
4412 KB |
Output is correct |
4 |
Correct |
10 ms |
4380 KB |
Output is correct |
5 |
Correct |
10 ms |
4372 KB |
Output is correct |
6 |
Correct |
10 ms |
4436 KB |
Output is correct |
7 |
Correct |
11 ms |
4436 KB |
Output is correct |
8 |
Correct |
9 ms |
4420 KB |
Output is correct |
9 |
Correct |
9 ms |
4436 KB |
Output is correct |
10 |
Correct |
12 ms |
4436 KB |
Output is correct |
11 |
Correct |
10 ms |
4436 KB |
Output is correct |
12 |
Correct |
10 ms |
4376 KB |
Output is correct |
13 |
Correct |
497 ms |
5332 KB |
Output is correct |
14 |
Correct |
537 ms |
5336 KB |
Output is correct |
15 |
Correct |
571 ms |
5328 KB |
Output is correct |
16 |
Correct |
514 ms |
5344 KB |
Output is correct |
17 |
Correct |
523 ms |
5328 KB |
Output is correct |
18 |
Correct |
508 ms |
5344 KB |
Output is correct |
19 |
Correct |
508 ms |
5348 KB |
Output is correct |
20 |
Correct |
493 ms |
5328 KB |
Output is correct |
21 |
Correct |
502 ms |
5328 KB |
Output is correct |
22 |
Correct |
502 ms |
5332 KB |
Output is correct |
23 |
Execution timed out |
4035 ms |
82556 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |