Submission #1023175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023175		dimashhh	Seats (IOI18_seats)	C++17	100 / 100	2454 ms	135820 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#pragma GCC optimize("O3")
const int inf = (int)1e9;
int n,m;
vector<vector<int>> f(N);
array<int,2> pos[N];
ll t[N * 4],add[N * 4];
int c[N * 4];
void build(int v = 1,int tl = 0,int tr = n * m - 1){
    c[v] = (tr - tl + 1);
    if(tl == tr) return;
    int tm = (tl + tr) >>1;
    build(v+v,tl,tm);
    build(v+v+1,tm+1,tr);
}
void inc(int v,ll val){
    t[v] += val;
    add[v] += val;
}
void push(int v){
    if(add[v]&&v + v+1 < N *4){
        inc(v+v,add[v]);
        inc(v+v+1,add[v]);
        add[v] = 0;
    }
}
void upd(int l,int r,int val,int v = 1,int tl = 0,int tr = n * m - 1){
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        inc(v,val); 
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,v+v,tl,tm);
        upd(l,r,val,v+v+1,tm+1,tr);
        t[v] = min(t[v + v],t[v + v + 1]);
        c[v] = (t[v +v] ==  t[v] ? c[v +v] : 0) + (t[v + v + 1] == t[v] ? c[v + v + 1] : 0);
    }
}
int get(int pos,int v = 1,int tl =0,int tr = n * m - 1){
    if(tl == tr) return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    if(pos <= tm) return get(pos,v+v,tl,tm);
    return get(pos,v+v+1,tm+1,tr);
}
int q(int x,int y){
    if(min(x,y) < 0 || x >= n || y >=m) return inf;
    return f[x][y];
}
void ad(int x,int y){
    vector<int> c = {q(x,y),q(x+1,y),q(x,y+1),q(x+1,y+1)};
    sort(c.begin(),c.end());
    if(c[0] != inf){
        upd(c[0],c[1] - 1,1);
    }
    if(c[2] != inf){
        upd(c[2],c[3] - 1,inf);
    } 
}
void del(int x,int y){
    vector<int> c = {q(x,y),q(x+1,y),q(x,y+1),q(x+1,y+1)};
    sort(c.begin(),c.end());
    if(c[0] != inf){
        upd(c[0],c[1] - 1,-1);
    }
    if(c[2] != inf){
        upd(c[2],c[3] - 1,-inf);
    }
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C){
    n = H;
    m = W;
    build();
    for(int i = 0;i < n;i++){
        f[i].resize(m + 1);
    }
    for(int i = 0;i < n * m;i++){
        f[R[i]][C[i]] = i;
        pos[i] = {R[i],C[i]};
    }
    for(int i = -1;i < n;i++){
        for(int j = -1;j < m;j++){
            ad(i,j);
        }
    }
}
void ad1(int x,int y){
    ad(x,y);
    ad(x-1,y);
    ad(x,y-1);
    ad(x-1,y-1);
}
void del1(int x,int y){
    del(x,y);
    del(x-1,y);
    del(x,y-1);
    del(x-1,y-1);
}
int swap_seats(int a, int b){
    array<int,2> x = pos[a];
    array<int,2> y = pos[b];
    del1(x[0],x[1]);
    del1(y[0],y[1]);
    swap(f[x[0]][x[1]],f[y[0]][y[1]]);
    ad1(x[0],x[1]);
    ad1(y[0],y[1]);
    swap(pos[a],pos[b]);
    // cout << get(0) << "x\n";
    // cout << "______________________\n";
    return c[1];
}

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