Submission #1107005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107005		snpmrnhlol	Seats (IOI18_seats)	C++17	100 / 100	3600 ms	154248 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int C = 6;
int seg[4*N][C];
int tmp[C];
int lz1[4*N],lz2[4*N];
int sz;
int n,m;
void pull(int node){
    for(int i = 0;i < C;i++){
        seg[node][i] = 0;
    }
    ///apply update
    for(int j = 0;j < 2;j++){
        if(!lz2[node*2 + j]){
            for(int i = 0;i < C;i++){
                seg[node][min(i + lz1[node*2 + j],5)]+=seg[node*2 + j][i];
            }
        }
    }
}
void upd(int ql, int qr, int tip, int nr, int l = 0, int r = sz - 1, int node = 1){
    if(r < ql || qr < l)return;
    if(ql <= l && r <= qr){
        if(tip == 0){
            lz1[node]+=nr;
        }else{
            lz2[node]+=nr;
        }
    }else{
        int mij = (l + r)/2;
        upd(ql, qr, tip, nr, l, mij, node*2);
        upd(ql, qr, tip, nr, mij + 1, r, node*2 + 1);
        pull(node);
    }
}
void build(int l = 0, int r = sz - 1, int node = 1){
    if(l != r){
        int mij = (l + r)/2;
        build(l, mij, node*2);
        build(mij + 1, r, node*2 + 1);
        pull(node);
    }else{
        seg[node][0] = 1;
    }
}
void dbg(int l = 0, int r = sz - 1, int node = 1){
    if(l != r){
        int mij = (l + r)/2;
        dbg(l, mij, node*2);
        dbg(mij + 1, r, node*2 + 1);
    }
    cout<<"debug"<<l<<' '<<r<<' '<<node<<' '<<lz1[node]<<' '<<lz2[node]<<' ';
    for(int i = 0;i < 6;i++){
        cout<<seg[node][i]<<' ';
    }
    cout<<'\n';
}
int query(){
    for(int i = 0;i < C;i++){
        tmp[i] = 0;
    }
    ///apply update
    if(!lz2[1]){
        for(int i = 0;i < C;i++){
            tmp[min(i + lz1[1],5)]+=seg[1][i];
        }
    }
    return tmp[4];
}
vector<vector<int>> v;
vector <int> x,y;
vector <int> tf;
void add2(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= m){
        tf.push_back(sz);
    }else{
        tf.push_back(v[x][y]);
    }
}
void add(int x, int y, int t){
    tf.clear();
    for(int i = x;i < x + 2;i++){
        for(int j = y;j < y + 2;j++){
            add2(i, j);
        }
    }
    sort(tf.begin(),tf.end());
    upd(tf[0], tf[1] - 1, 0, t);
    upd(tf[2], tf[3] - 1, 1, t);
}
void give_initial_chart(int n2, int m2, std::vector<int> a, std::vector<int> b) {
    n = n2;m = m2;
    v.assign(n, vector<int>(m,0));
    x = a;y = b;
    sz = n*m;
    for(int i = 0;i < n*m;i++){
        v[x[i]][y[i]] = i;
    }
    build();
    for(int i = -1;i < n;i++){
        for(int j = -1;j < m;j++){
            add(i, j, 1);
        }
    }
    //cout<<query()<<'\n';
    //dbg();
}
int prevans = -1;
int swap_seats(int a, int b){
    if(a > b)swap(a,b);
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    swap(v[x[a]][y[a]],v[x[b]][y[b]]);
    ///add update
    for(int i = x[a] - 1;i < x[a] + 1;i++){
        for(int j = y[a] - 1;j < y[a] + 1;j++){
            add(i, j, 1);
        }
    }
    for(int i = x[b] - 1;i < x[b] + 1;i++){
        for(int j = y[b] - 1;j < y[b] + 1;j++){
            add(i, j, 1);
        }
    }
    swap(v[x[a]][y[a]],v[x[b]][y[b]]);
    ///remove old update
    for(int i = x[a] - 1;i < x[a] + 1;i++){
        for(int j = y[a] - 1;j < y[a] + 1;j++){
            add(i, j, -1);
        }
    }
    for(int i = x[b] - 1;i < x[b] + 1;i++){
        for(int j = y[b] - 1;j < y[b] + 1;j++){
            add(i, j, -1);
        }
    }
    swap(v[x[a]][y[a]],v[x[b]][y[b]]);
    return query();
}
/**
1 1 1
0 0

0 0


2 3 2
0 0
1 0
1 1
0 1
0 2
1 2

0 5
0 5
**/

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