| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 422002 |
2021-06-09T14:39:29 Z |
Bill_00 |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
210360 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define INF INT_MAX
using namespace std;
int lazy[4000000][2],r[1000000],c[1000000],a[4000000],H,W;
vector<pair<pair<int,int>,int>>node[4000000];
vector<pair<pair<int,int>,int> >combine(vector<pair<pair<int,int>,int> >l,vector<pair<pair<int,int>,int> >r){
map<pair<int,int>,int>um;
vector<pair<pair<int,int>,int> >ans;
vector<pair<int,int> >p;
for(int i=0;i<l.size();i++){
p.push_back(l[i].ff);
um[l[i].ff]=l[i].ss;
}
for(int i=0;i<r.size();i++){
p.push_back(r[i].ff);
um[r[i].ff]+=r[i].ss;
}
sort(p.begin(),p.end());
for(int i=0;i<p.size();i++){
if(ans.size()==0 || ans.back().ff!=p[i]){
ans.push_back({p[i],um[p[i]]});
}
if(ans.size()==5) break;
}
return ans;
}
void build(int id,int l,int r){
if(l==r){
node[id].push_back({{0,0},1});
return;
}
int m=l+r>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
node[id]=combine(node[id*2],node[id*2+1]);
}
void update(int id,int l,int r,int L,int R,bool type,int val){
if(type==0){
for(int i=0;i<node[id].size();i++){
node[id][i].ff.ss+=lazy[id][type];
}
if(l!=r){
lazy[id*2][type]+=lazy[id][type];
lazy[id*2+1][type]+=lazy[id][type];
}
lazy[id][type]=0;
}
else{
for(int i=0;i<node[id].size();i++){
node[id][i].ff.ff+=lazy[id][type];
}
if(l!=r){
lazy[id*2][type]+=lazy[id][type];
lazy[id*2+1][type]+=lazy[id][type];
}
lazy[id][type]=0;
}
if(r<L || R<l) return;
if(L<=l && r<=R){
for(int i=0;i<node[id].size();i++){
if(type) node[id][i].ff.ff+=val;
else node[id][i].ff.ss+=val;
}
if(l!=r){
lazy[id*2][type]+=val;
lazy[id*2+1][type]+=val;
}
return;
}
int m=l+r>>1;
update(id*2,l,m,L,R,type,val);
update(id*2+1,m+1,r,L,R,type,val);
node[id]=combine(node[id*2],node[id*2+1]);
}
void give_initial_chart(int h, int w,vector<int> R,vector<int> C){
H=h;
W=w;
build(1,0,H*W-1);
for(int i=0;i<R.size();i++){
r[i]=R[i]+1;
c[i]=C[i]+1;
a[(R[i]+1)*(W+2)+C[i]+1]=i;
// cout << R[i]+1 << ' ' << C[i]+1 << ' ' << (R[i]+1)*(W+2)+C[i]+1 << '\n';
}
for(int i=0;i<=W+1;i++){
a[i]=INF;
a[(H+1)*(W+2)+i]=INF;
}
for(int i=0;i<=H+1;i++){
a[i*(W+2)]=INF;
a[i*(W+2)+W+1]=INF;
}
for(int i=1;i<=H+1;i++){
for(int j=1;j<=W+1;j++){
vector<int>v;
v.push_back(a[i*(W+2)+j]);
v.push_back(a[(i-1)*(W+2)+j]);
v.push_back(a[i*(W+2)+j-1]);
v.push_back(a[(i-1)*(W+2)+j-1]);
sort(v.begin(),v.end());
// printf("%d %d %d %d %d\n",v[0],v[1],v[2],v[3],101000000);
update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
}
}
}
pair<int,int>answer={0,4};
int swap_seats(int A, int B){
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int x=r[A]+i;
int y=c[A]+j;
vector<int>v;
v.push_back(a[x*(W+2)+y]);
v.push_back(a[(x-1)*(W+2)+y]);
v.push_back(a[x*(W+2)+y-1]);
v.push_back(a[(x-1)*(W+2)+y-1]);
sort(v.begin(),v.end());
update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,-1);
if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,-1);
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int x=r[B]+i;
int y=c[B]+j;
vector<int>v;
v.push_back(a[x*(W+2)+y]);
v.push_back(a[(x-1)*(W+2)+y]);
v.push_back(a[x*(W+2)+y-1]);
v.push_back(a[(x-1)*(W+2)+y-1]);
sort(v.begin(),v.end());
update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,-1);
if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,-1);
}
}
swap(a[r[A]*(W+2)+c[A]],a[r[B]*(W+2)+c[B]]);
swap(r[A],r[B]);
swap(c[A],c[B]);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int x=r[A]+i;
int y=c[A]+j;
vector<int>v;
v.push_back(a[x*(W+2)+y]);
v.push_back(a[(x-1)*(W+2)+y]);
v.push_back(a[x*(W+2)+y-1]);
v.push_back(a[(x-1)*(W+2)+y-1]);
sort(v.begin(),v.end());
update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int x=r[B]+i;
int y=c[B]+j;
vector<int>v;
v.push_back(a[x*(W+2)+y]);
v.push_back(a[(x-1)*(W+2)+y]);
v.push_back(a[x*(W+2)+y-1]);
v.push_back(a[(x-1)*(W+2)+y-1]);
sort(v.begin(),v.end());
update(1,0,H*W-1,v[0],min(v[1],H*W)-1,0,1);
if(v[2]!=INF) update(1,0,H*W-1,v[2],min(H*W,v[3])-1,1,1);
}
}
for(pair<pair<int,int>,int>to:node[1]){
if(to.ff==answer) return to.ss;
}
return 0;
}
Compilation message
seats.cpp: In function 'std::vector<std::pair<std::pair<int, int>, int> > combine(std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<std::pair<int, int>, int> >)':
seats.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<l.size();i++){
| ~^~~~~~~~~
seats.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0;i<r.size();i++){
| ~^~~~~~~~~
seats.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<p.size();i++){
| ~^~~~~~~~~
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:35:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m=l+r>>1;
| ~^~
seats.cpp: In function 'void update(int, int, int, int, int, bool, int)':
seats.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<node[id].size();i++){
| ~^~~~~~~~~~~~~~~~
seats.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<node[id].size();i++){
| ~^~~~~~~~~~~~~~~~
seats.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<node[id].size();i++){
| ~^~~~~~~~~~~~~~~~
seats.cpp:73:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int m=l+r>>1;
| ~^~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0;i<R.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
94372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
94372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4073 ms |
210360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4051 ms |
96024 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
736 ms |
95880 KB |
Output is correct |
| 2 |
Correct |
2079 ms |
95880 KB |
Output is correct |
| 3 |
Execution timed out |
4103 ms |
95656 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
388 ms |
94372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
