Submission #985222

#	Time	Username	Problem	Language	Result	Execution time	Memory
985222		oolimry	Seats (IOI18_seats)	C++17	25 / 100	4102 ms	80300 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector<int> R;
vector<int> C;

int lv1[1100100 * 4];
int rv1[1100100 * 4];
int lv2[1100100 * 4];
int rv2[1100100 * 4];

void hupdate(int i, int s, int e, int in, int k){
    if(s == e){
        lv1[i] = k;
        rv1[i] = k;
        return;
    }

    int m = (s + e)/2;

    if(in <= m){
        hupdate(i * 2,s,m,in,k);
    }
    else{
        hupdate(i * 2 + 1,m + 1, e, in, k);
    }

    lv1[i] = min(lv1[i * 2], lv1[i * 2 + 1]);
    rv1[i] = max(rv1[i * 2], rv1[i * 2 + 1]);
}

pair<int,int> hquery(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return  {lv1[i],rv1[i]};
    }

    int m = (s + e)/2;

    pair<int,int> ii = {1100100100, -1};

    if(S <= m){
        pair<int,int> ii1 = hquery(i * 2,s,m,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }
    if(m < E){
        pair<int,int> ii1 = hquery(i * 2 + 1,m + 1,e,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }

    return ii;
}

void cupdate(int i, int s, int e, int in, int k){
    if(s == e){
        lv2[i] = k;
        rv2[i] = k;
        return;
    }

    int m = (s + e)/2;

    if(in <= m){
        cupdate(i * 2,s,m,in,k);
    }
    else{
        cupdate(i * 2 + 1,m + 1, e, in, k);
    }

    lv2[i] = min(lv2[i * 2], lv2[i * 2 + 1]);
    rv2[i] = max(rv2[i * 2], rv2[i * 2 + 1]);
}

pair<int,int> cquery(int i, int s, int e, int S, int E){
    if(S <= s && e <= E){
        return  {lv2[i],rv2[i]};
    }

    int m = (s + e)/2;

    pair<int,int> ii = {1100100100, -1};

    if(S <= m){
        pair<int,int> ii1 = cquery(i * 2,s,m,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }
    if(m < E){
        pair<int,int> ii1 = cquery(i * 2 + 1,m + 1,e,S,E);

        ii.first = min(ii.first, ii1.first);
        ii.second = max(ii.second, ii1.second);
    }

    return ii;
}


int H,W;
int HW;

void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
    R = R_;
    C = C_;
    H = H_;
    W = W_;

    HW = H * W;

    for(int i = 0; i < H * W ; i++){
        hupdate(1,0,HW-1,i,R[i]);
        cupdate(1,0,HW-1,i,C[i]);
    }
}

int swap_seats(int a, int b) {
    swap(R[a],R[b]);
    swap(C[a],C[b]);

    hupdate(1,0,HW-1,a,R[a]);
    hupdate(1,0,HW-1,b,R[b]);

    cupdate(1,0,HW-1,a,C[a]);
    cupdate(1,0,HW-1,b,C[b]);


    int num = 2;

    int v = 2;
    int s = 1;
    int e = 1;

    while(v < H * W){
        pair<int,int> ii = hquery(1,0,HW-1,0, v - 1);
        pair<int,int> ii1 = cquery(1,0,HW-1,0, v - 1);

        s = (ii.second - ii.first + 1);
        e = (ii1.second - ii1.first + 1);

        if( s * e == v ){
            v = min( (s + 1) * e, s * (e + 1) );
            num++;
        }

        v = max(v, s * e);
    }

    return num;
}

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