Submission #991410

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

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
array<int,3> merge(array<int,3> a,array<int,3> b){
  array<int,3> c={0,0,0};
  c[0]=a[0]+b[0];
  c[1]=min(a[1],b[1]+a[0]);
  if(c[1]==a[1]) c[2]+=a[2];
  if(c[1]==b[1]+a[0]) c[2]+=b[2];
  return c;
}
array<int,3> e(){
  return {0,1000000000,0};
}
struct segtree{
  vector<array<int,3>> 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]={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,array<int,3> v){
    x+=n;
    nod[x]=v;
    while(x>1){
      x/=2;
      nod[x]=merge(nod[2*x],nod[2*x+1]);
    }
  }
  array<int,3> prod(int l,int r,int a,int b,int k){
    if(r<=a||b<=l) return e();
    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));
  }
  array<int,3> 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];
void addv(int x,int v){
  auto r=sg.prod(x,x+1);
  r[0]+=v;
  r[1]+=v;
  //cout<<x<<" "<<v<<endl;
  sg.set(x,r);
}
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)[2];
}

Compilation message (stderr)

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