Submission #991412

#	Time	Username	Problem	Language	Result	Execution time	Memory
991412		PCTprobability	Seats (IOI18_seats)	C++17	0 / 100	4069 ms	20136 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define nd node
struct node{
  int sum,mn,cnt;
  node(){
    sum=0,mn=1000000000,cnt=0;
  }
  node(int a,int b,int c){
    sum=a,mn=b,cnt=c;
  }
};
node merge(node a,node b){
  node c;
  c.sum=a.sum+b.sum;
  c.mn=min(a.mn,b.mn+a.sum);
  if(c.mn==a.mn) c.cnt+=a.cnt;
  if(c.mn==b.mn+a.sum) c.cnt+=b.cnt;
  return c;
}
struct segtree{
  vector<nd> nod;
  int n;
  segtree(){
  }
  segtree(int n_){
    n=1;
    while(n<n_) n*=2;
    nod.resize(2*n);
    for(int i=0;i<2*n;i++) nod[i]=nd(0,0,1);
    for(int i=n-1;i>=0;i--) nod[i]=merge(nod[2*i],nod[2*i+1]);
  }
  void set(int x,nd v){
    x+=n;
    nod[x]=v;
    while(x>1){
      x/=2;
      nod[x]=merge(nod[2*x],nod[2*x+1]);
    }
  }
  nd prod(int l,int r,int a,int b,int k){
    if(r<=a||b<=l) return nd();
    if(l<=a&&b<=r) return nod[k];
    return merge(prod(l,r,a,(a+b)/2,2*k),prod(l,r,(a+b)/2,b,2*k+1));
  }
  nd prod(int l,int r){
    return prod(l,r,0,n,1);
  }
};
segtree sg;
int n,m;
vector<int> c,r;
vector<int> rv;
int ans=0;
set<int> rs[1010],cs[1010];
int val[1010101];
void addv(int x,int v){
  val[x]+=v;
  sg.set(x,{val[x],val[x],1});
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n=H,m=W;
  rv.resize(m);
  for(int i=0;i<m;i++) rv[C[i]]=i;
  r=C;
  C=rv;
  C.push_back(m);
  reverse(C.begin(),C.end());
  C.push_back(m);
  reverse(C.begin(),C.end());
  c=C;
  segtree seg(m+10);
  sg=seg;
  //0/1 1/2 ... m-1/m
  for(int i=0;i+1<c.size();i++){
    int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
    addv(x,1);
    addv(y,-1);
  }
  //for(auto e:c) cout<<e<<" ";
  //cout<<endl;
}
int swap_seats(int a, int b) {
  int ans=0;
  //r[a] と r[b] にいるのを swap する
  set<int> s;
  s.insert(r[a]+2);
  s.insert(r[a]);
  s.insert(r[a]+1);
  s.insert(r[b]+2);
  s.insert(r[b]);
  s.insert(r[b]+1);
  //cout<<"A"<<" "<<a<<" "<<b<<endl;
  //for(auto e:s) cout<<e<<" ";
 // cout<<endl;
  for(auto i:s){
    if(i<0||i+1>=c.size()) continue;
    int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
    addv(x,-1);
    addv(y,1);
  }
  swap(c[r[a]+1],c[r[b]+1]);
  swap(r[a],r[b]);
 // for(auto e:c) cout<<e<<" ";
 // cout<<endl;
  for(auto i:s){
    if(i<0||i+1>=c.size()) continue;
    int x=min(c[i],c[i+1]),y=max(c[i],c[i+1]);
    addv(x,1);
    addv(y,-1);
  }
  for(int i=0;i<=m;i++){
    auto v=sg.prod(i,i+1);
    //cout<<v.sum<<" "<<v.mn<<" "<<v.cnt<<endl;
  }
  return sg.prod(0,m).cnt;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i=0;i+1<c.size();i++){
      |               ~~~^~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:98:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     if(i<0||i+1>=c.size()) continue;
      |             ~~~^~~~~~~~~~
seats.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     if(i<0||i+1>=c.size()) continue;
      |             ~~~^~~~~~~~~~
seats.cpp:114:10: warning: variable 'v' set but not used [-Wunused-but-set-variable]
  114 |     auto v=sg.prod(i,i+1);
      |          ^
seats.cpp:85:7: warning: unused variable 'ans' [-Wunused-variable]
   85 |   int ans=0;
      |       ^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30