#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1000005;
pair<ll,ll> t[maxn*4];
ll lazy[maxn*4],lock2[maxn*4];
ll h,w,n;
vector<ll> c;
ll pos[maxn];
void build(ll a[], ll tl, ll tr, ll v){
if (tl==tr){
t[v].first = a[tl];
t[v].second = 1;
}
else{
ll tm = (tl+tr)>>1;
build(a,tl,tm,v*2);
build(a,tm+1,tr,v*2+1);
if (t[v*2].first==t[v*2+1].first){
t[v].first = t[v*2].first;
t[v].second = t[v*2].second+t[v*2+1].second;
}
else if (t[v*2].first>t[v*2+1].first){
t[v].first = t[v*2+1].first;
t[v].second = t[v*2+1].second;
}
else{
t[v].first = t[v*2].first;
t[v].second = t[v*2].second;
}
}
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll x){
// if (tl==0&&tr==n-1){
// cout << "adding " << x << " to " << l << "," << r << "\n";
// }
if (lazy[v]!=0){
if (lock2[v]==1){
t[v].first = lazy[v];
t[v].second = tr-tl+1;
if (tl!=tr){
lazy[v*2] = lazy[v];
lazy[v*2+1] = lazy[v];
lock2[v*2] = 1;
lock2[v*2+1] = 1;
}
lock2[v] = 0;
}
else{
t[v].first += lazy[v];
if (tl!=tr){
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
}
}
lazy[v] = 0;
}
if (tr<l||tl>r) return;
if (tl>=l&&tr<=r){
t[v].first += x;
lazy[v*2] += x;
lazy[v*2+1] += x;
return;
}
ll tm = (tl+tr)>>1;
update(v*2,tl,tm,l,r,x);
update(v*2+1,tm+1,tr,l,r,x);
if (t[v*2].first==t[v*2+1].first){
t[v].first = t[v*2].first;
t[v].second = t[v*2].second+t[v*2+1].second;
}
else if (t[v*2].first>t[v*2+1].first){
t[v].first = t[v*2+1].first;
t[v].second = t[v*2+1].second;
}
else{
t[v].first = t[v*2].first;
t[v].second = t[v*2].second;
}
return;
}
pair<ll,ll> query(ll v, ll tl, ll tr, ll l, ll r){
if (lazy[v]!=0){
if (lock2[v]==1){
t[v].first = lazy[v];
t[v].second = tr-tl+1;
if (tl!=tr){
lazy[v*2] = lazy[v];
lazy[v*2+1] = lazy[v];
lock2[v*2] = 1;
lock2[v*2+1] = 1;
}
lock2[v] = 0;
}
else{
t[v].first += lazy[v];
if (tl!=tr){
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
}
}
lazy[v] = 0;
}
if (tr<l||tl>r) return {INT_MAX,0};
if (tl>=l&&tr<=r){
return t[v];
}
ll tm = (tl+tr)>>1;
pair<ll,ll> t1 = query(v*2,tl,tm,l,r);
pair<ll,ll> t2 = query(v*2+1,tm+1,tr,l,r);
pair<ll,ll> ans;
if (t1.first==t2.first){
ans.first = t1.first;
ans.second = t1.second+t2.second;
}
else if (t1.first>t2.first){
ans.first = t2.first;
ans.second = t2.second;
}
else{
ans.first = t1.first;
ans.second = t1.second;
}
return ans;
}
void set2(ll v, ll tl, ll tr, ll l, ll r, ll x){
if (lazy[v]!=0){
if (lock2[v]==1){
t[v].first = lazy[v];
t[v].second = tr-tl+1;
if (tl!=tr){
lazy[v*2] = lazy[v];
lazy[v*2+1] = lazy[v];
lock2[v*2] = 1;
lock2[v*2+1] = 1;
}
lock2[v] = 0;
}
else{
t[v].first += lazy[v];
if (tl!=tr){
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
}
}
lazy[v] = 0;
}
if (tr<l||tl>r) return;
if (tl>=l&&tr<=r){
t[v].first = x;
t[v].second = tr-tl+1;
lazy[v*2] = x;
lazy[v*2+1] = x;
lock2[v*2] = 1;
lock2[v*2+1] = 1;
return;
}
ll tm = (tl+tr)>>1;
set2(v*2,tl,tm,l,r,x);
set2(v*2+1,tm+1,tr,l,r,x);
if (t[v*2].first==t[v*2+1].first){
t[v].first = t[v*2].first;
t[v].second = t[v*2].second+t[v*2+1].second;
}
else if (t[v*2].first>t[v*2+1].first){
t[v].first = t[v*2+1].first;
t[v].second = t[v*2+1].second;
}
else{
t[v].first = t[v*2].first;
t[v].second = t[v*2].second;
}
return;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
n=h*w;
ll a[n];
memset(a,0,sizeof(a));
build(a,0,n-1,1);
for (int i=0;i<n;i++){
c.push_back(C[i]);
pos[C[i]]=i;
}
pos[n] = n;
set2(1,0,n-1,pos[0],n-1,1);
// for (int i=0;i<n;i++){
// cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " ";
// }
// cout << "\n";
for (int i=0;i<n;i++){
ll a=pos[i],b=pos[i+1];
if (a>b){
ll temp = a;
a=b;
b=temp;
}
update(1,0,n-1,a,b-1,1);
// for (int i=0;i<n;i++){
// cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " ";
// }
// cout << "\n";
}
// for (int i=0;i<n;i++){
// cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " ";
// }
// cout << "\n";
}
int swap_seats(int a, int b) {
ll a2 = c[a];
ll b2 = c[b];
if (a2==0){
update(1,0,n-1,a,n-1,-1);
ll temp = pos[1];
if (a>temp) update(1,0,n-1,temp,a-1,-1);
else update(1,0,n-1,a,temp-1,-1);
}
else{
ll temp = pos[a2-1];
if (a>temp) update(1,0,n-1,temp,a-1,-1);
else update(1,0,n-1,a,temp-1,-1);
temp = pos[a2+1];
if (a>temp) update(1,0,n-1,temp,a-1,-1);
else update(1,0,n-1,a,temp-1,-1);
}
if (b2==0){
update(1,0,n-1,b,n-1,-1);
ll temp = pos[1];
if (b>temp) update(1,0,n-1,temp,b-1,-1);
else update(1,0,n-1,b,temp-1,-1);
}
else{
ll temp = pos[b2-1];
if (b>temp) update(1,0,n-1,temp,b-1,-1);
else update(1,0,n-1,b,temp-1,-1);
temp = pos[b2+1];
if (b>temp) update(1,0,n-1,temp,b-1,-1);
else update(1,0,n-1,b,temp-1,-1);
}
pos[a2] = b;
pos[b2] = a;
c[a] = b2;
c[b] = a2;
if (a2==0){
//new
ll temp = pos[1];
update(1,0,n-1,b,n-1,1);
if (b>temp) update(1,0,n-1,temp,b-1,1);
else update(1,0,n-1,b,temp-1,1);
}
else{
//new
ll temp = pos[a2-1];
if (b>temp) update(1,0,n-1,temp,b-1,1);
else update(1,0,n-1,b,temp-1,1);
temp = pos[a2+1];
if (b>temp) update(1,0,n-1,temp,b-1,1);
else update(1,0,n-1,b,temp-1,1);
}
if (b2==0){
//new
ll temp = pos[1];
update(1,0,n-1,a,n-1,1);
if (a>temp) update(1,0,n-1,temp,a-1,1);
else update(1,0,n-1,a,temp-1,1);
}
else{
//new
ll temp = pos[b2-1];
if (a>temp) update(1,0,n-1,temp,a-1,1);
else update(1,0,n-1,a,temp-1,1);
temp = pos[b2+1];
if (a>temp) update(1,0,n-1,temp,a-1,1);
else update(1,0,n-1,a,temp-1,1);
}
// for (int i=0;i<n;i++){
// cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " ";
// }
// cout << "\n";
return query(1,0,n-1,0,n-1).second;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
233 ms |
111856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
5724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
40 ms |
6104 KB |
Output is correct |
| 3 |
Correct |
62 ms |
6232 KB |
Output is correct |
| 4 |
Correct |
83 ms |
8212 KB |
Output is correct |
| 5 |
Correct |
158 ms |
7428 KB |
Output is correct |
| 6 |
Incorrect |
597 ms |
121012 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
