Submission #808291

#	Time	Username	Problem	Language	Result	Execution time	Memory
808291		Supersonic	Seats (IOI18_seats)	C++14	17 / 100	4054 ms	83684 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> g;int h,w;int n;
pair<ll,ll> cmi[1000001];pair<ll,ll> cmx[1000001];
int cl[1000001],cr[1000001],cu[1000001],cd[1000001];


struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    void add(int idx, int val) {
      for (++idx; idx < n; idx += idx & -idx)
          bit[idx] += val;
    }

    void range_add(int l, int r, int val) {
        add(l, val);
        add(r + 1, -val);
    }

    int point_query(int idx) {
        int ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }

};

FenwickTree tf(1000010);

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h=H;w=W;n=h*w;for(int i=0;i<n;i++){g.push_back({R[i],C[i]});}
  //tf=FenwickTree(1000001);
  /*tf.range_add(0,1000,5);
  tf.range_add(5,1000,5);
  cerr<<tf.point_query(2)<<' '<<tf.point_query(8)<<endl;*/
  //exit(1);


  pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
  int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
  long long t=0;
  for(int i=0;i<=n;i++){
    mi=min(mi,g[i]);mx=max(mx,g[i]);
    if(g[i].second<lm)lm=g[i].second;
    if(g[i].second>rm)rm=g[i].second;
    if(g[i].first<um)um=g[i].first;
    if(g[i].first>dm)dm=g[i].first;
    //cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
    if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
    cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
    
    int c=tf.point_query(i);
    tf.add(i,t-c);
  }



}

int swap_seats(int a, int b) {
  
  swap(g[a],g[b]);
  pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
  int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
  long long t=0;
  if(a>b)swap(a,b);
  if(a>0&&b>0){int i=a-1;t=tf.point_query(i);mi=cmi[i];mx=cmx[i];lm=cl[i];rm=cr[i];um=cu[i];dm=cd[i];}
  int bb=-1;
  for(int i=a;i<=b;i++){
    mi=min(mi,g[i]);mx=max(mx,g[i]);
    if(g[i].second<lm)lm=g[i].second;
    if(g[i].second>rm)rm=g[i].second;
    if(g[i].first<um)um=g[i].first;
    if(g[i].first>dm)dm=g[i].first;
    //cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
    if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
    cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
    
    int c=tf.point_query(i);
    tf.add(i,t-c);
    if(i==b)bb=t-c;
    //cerr<<lm<<'-'<<um<<'-'<<rm<<'-'<<dm<<endl;
    //cerr<<(lm-rm)<<' '<<mx.second-mi.second<<endl;
    //cerr<<(lm-rm==mx.second-mi.second)<<' '<<(dm-um==mx.first-mi.first)<<endl;
  }
  tf.range_add(b+1,n,bb);
  return tf.point_query(n-1);
}
/*
2 3 3
0 0
1 0
1 1
0 1
0 2
1 2
1 4
0 5
0 1

*/

/*

0 3 1
4 2 5

5 3 1
4 2 0

5 3 0
4 2 1
*/

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