Submission #1245716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245716		matisito	Seats (IOI18_seats)	C++20	17 / 100	4094 ms	149696 KiB

seats

#include "seats.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
using T=pair<pair<long long, long long>, pair<long long, long long>>;

vector<int> r;
struct segtree{
  int n;
  vector<int>st;
  segtree (int n):n(n), st(2*n){}
  void update(int posi, int val){
    for(st[posi+=n]=val ; posi>1 ; posi/=2) st[posi/2]=st[posi]+st[posi^1];
  }
  int querie(int l, int r){
    r++;
    int res=0;
    for(l+=n, r+=n ; l<r ; l/=2, r/=2){
      if(l&1) res+=st[l++];
      if(r&1) res+=st[--r];
    }
    return res;
  }
}st(1000006);

vector<vector<long long>>pref;
vector<pair<int, int>>position;
vector<T>dp;
int maximo, h, w;

void updateY(int x, int y, long long val){
  while(y<=w){
    pref[x][y]+=val;
    y+=y&-y;
  }
}
void update(int x, int y, long long val){
  while(x<=h){
    updateY(x, y, val);
    x+=x&-x;
  }
}
long long querieY(int x, int y){
  long long res=0;
  while(y>0){
    res+=pref[x][y];
    y-=y&-y;
  }
  return res;
}

long long querie(int x, int y){
  long long res=0;
  while(x>0){
    res+=querieY(x, y);
    x-=x&-x;
  }
  return res;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  maximo=H*W;
  h=H;
  w=W;
  position.push_back({0, 0});
  pref.resize(H+5, vector<long long>(W+5));
  dp.resize(H*W + 10);
  for(int i=0 ; i<H*W ; i++){
    // pref[R[i]+1][C[i]+1]=i+1;
    update(R[i]+1, C[i]+1, i+1);
    position.push_back({R[i]+1, C[i]+1});
  }
  // for(int i=1 ; i<=H ; i++){
  //   for(int j=1 ; j<=W ; j++) pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
  // }
  for(int i=1 ; i<=H*W ; i++){
    if(i==1){
      T uwu;
      uwu.first={position[i].first, position[i].second};
      uwu.second=uwu.first;
      dp[i]=uwu;
    }else{
      T uwu;
      uwu=dp[i-1];
      uwu.first.first=min(uwu.first.first, (long long)position[i].first);
      uwu.first.second=min(uwu.first.second, (long long)position[i].second);
      uwu.second.first=max(uwu.second.first, (long long)position[i].first);
      uwu.second.second=max(uwu.second.second, (long long)position[i].second);
      dp[i]=uwu;
    }
    long long vale=dp[i].second.first-dp[i].first.first+1, notta=dp[i].second.second-dp[i].first.second+1;
    long long vn=vale*notta;
    if(vn==i){
      st.update(i, 1);
      // dbg(i)
    }else{
      st.update(i, 0);
      // dbg(i);
    }
  }
}

int swap_seats(int a, int b) {
  a++; b++;
  if(a>b) swap(a, b);
  update(position[a].first, position[a].second, b-a);
  update(position[b].first, position[b].second, a-b);
  swap(position[a], position[b]);
  for(int i=a ; i<=b ; i++){
    if(i==1){
      T uwu;
      uwu.first={position[i].first, position[i].second};
      uwu.second=uwu.first;
      dp[i]=uwu;
    }else{
      T uwu;
      uwu=dp[i-1];
      uwu.first.first=min(uwu.first.first, (long long)position[i].first);
      uwu.first.second=min(uwu.first.second, (long long)position[i].second);
      uwu.second.first=max(uwu.second.first, (long long)position[i].first);
      uwu.second.second=max(uwu.second.second, (long long)position[i].second);
      dp[i]=uwu;
    }
    long long vale=dp[i].second.first-dp[i].first.first+1, notta=dp[i].second.second-dp[i].first.second+1;
    long long vn=vale*notta;
    // vn=(vn*(vn+1))/2;
    if(i==4){
      // dbg(vn)
    }
    if(vn==i){
      st.update(i, 1);
      // dbg(i)
    }else{
      st.update(i, 0);
      // dbg(i);
    }
  }
  // dbg(maximo)
  return st.querie(1, maximo);
  return 0;
}

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