Submission #1220473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220473		Malix	Seats (IOI18_seats)	C++20	33 / 100	286 ms	75060 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi a,arr,X;
int n;
vector<ti> st;
//cnt,min,sum

void build(int x,int l,int r){
  if(l==r){
    st[x]={1,a[l],a[l]};
    return;
  }
  int m=(l+r)/2;
  build(2*x,l,m);
  build(2*x+1,m+1,r);
  auto [p1,q1,r1]=st[2*x];
  auto [p2,q2,r2]=st[2*x+1];
  q2+=r1;
  if(q1==q2)st[x]={p1+p2,q1,r1+r2};
  else if(q1<q2)st[x]={p1,q1,r1+r2};
  else st[x]={p2,q2,r1+r2};
}

void update(int x,int l,int r,int p,int v){
  if(l==r){
    st[x]={1,v,v};
    return;
  }
  int m=(l+r)/2;
  if(m>=p)update(2*x,l,m,p,v);
  else update(2*x+1,m+1,r,p,v);
  auto [p1,q1,r1]=st[2*x];
  auto [p2,q2,r2]=st[2*x+1];
  q2+=r1;
  if(q1==q2)st[x]={p1+p2,q1,r1+r2};
  else if(q1<q2)st[x]={p1,q1,r1+r2};
  else st[x]={p2,q2,r1+r2};
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n=W;
  X=C;
  a.resize(n,0);arr.resize(n);
  REP(i,0,n)arr[X[i]]=i;
  REP(i,0,n){
    if(X[i]-1<0||arr[X[i]-1]>arr[X[i]])a[i]++;
    else a[i]--;
    if(X[i]+1>=n||arr[X[i]+1]>arr[X[i]])a[i]++;
    else a[i]--;
  }
  st.resize(4*n+1);
  build(1,0,n-1);
}

int swap_seats(int x, int y) {
  swap(arr[X[x]],arr[X[y]]);
  swap(X[x],X[y]);
  x=X[x];y=X[y];
  for(int i=max(0,x-1);i<=min(n-1,x+1);i++){
    a[arr[i]]=0;
    if(i-1<0||arr[i-1]>=arr[i])a[arr[i]]++;
    else a[arr[i]]--;
    if(i+1>=n||arr[i+1]>=arr[i])a[arr[i]]++;
    else a[arr[i]]--;
    update(1,0,n-1,arr[i],a[arr[i]]);
  }
  for(int i=max(0,y-1);i<=min(n-1,y+1);i++){
    a[arr[i]]=0;
    if(i-1<0||arr[i-1]>=arr[i])a[arr[i]]++;
    else a[arr[i]]--;
    if(i+1>=n||arr[i+1]>=arr[i])a[arr[i]]++;
    else a[arr[i]]--;
    update(1,0,n-1,arr[i],a[arr[i]]);
  }
  if(get<1>(st[1])==2)return get<0>(st[1]);
  return 0;
}

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