Submission #91759

#	Time	Username	Problem	Language	Result	Execution time	Memory
91759		Retro3014	Seats (IOI18_seats)	C++17	17 / 100	4027 ms	157512 KiB

seats

#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>


using namespace std;
#define MAX_N 1000000
#define INF 1000000000
typedef long long ll;

struct S{
    int x, y;
};
int h, w, N;
struct T{
    int data, lazy;
    int cnt, ans, mini;
    int s, e;
    int l, r;
};

vector<T> seg(1);
vector<S> v;
vector<int> r;

vector<S> s, e;
int ans;
vector<vector<int>> arr;

deque<int> dq;

void init(int x){
    dq.push_back(x);
    while(!dq.empty()){
        x=dq.front(); dq.pop_front();
        if(seg[x].s==seg[x].e)  return;
        if(seg[x].l==-1){
            seg[x].l=(int)seg.size();
            seg.push_back(seg[0]);
            seg.back().s = seg[x].s; seg.back().e = (seg[x].s+seg[x].e)/2;
            seg.back().cnt = seg.back().e-seg.back().s+1; seg.back().ans = seg.back().cnt;
            seg.back().l = -1; seg.back().r = -1;
            init(seg[x].l);
        }
        if(seg[x].r==-1){
            seg[x].r=(int)seg.size();
            seg.push_back(seg[0]);
            seg.back().s = (seg[x].s+seg[x].e)/2+1; seg.back().e = seg[x].e;
            seg.back().cnt = seg.back().e-seg.back().s+1; seg.back().ans = seg.back().cnt;
            seg.back().l = -1; seg.back().r = -1;
            init(seg[x].r);
        }
    }
}

void update1(int idx){
    if(idx==-1) return;
    if(seg[idx].lazy!=0){
        if(seg[idx].l!=-1){
            seg[seg[idx].l].lazy += seg[idx].lazy;
            seg[seg[idx].l].mini += seg[idx].lazy;
        }
        if(seg[idx].r!=-1){
            seg[seg[idx].r].lazy += seg[idx].lazy;
            seg[seg[idx].r].mini += seg[idx].lazy;
        }
        seg[idx].lazy = 0;
    }
}

void update2(int idx){
    if(idx==-1) return;
    if(seg[idx].l==-1 && seg[idx].r==-1)    return;
    if(seg[idx].l==-1){
        seg[idx].ans = seg[seg[idx].r].ans;
        seg[idx].mini = seg[seg[idx].r].mini;
        return;
    }
    if(seg[idx].r==-1){
        seg[idx].ans = seg[seg[idx].l].ans;
        seg[idx].mini = seg[seg[idx].l].mini;
        return;
    }
    if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
        seg[idx].ans = seg[seg[idx].r].ans;
        seg[idx].mini = seg[seg[idx].r].mini;
        return;
    }
    if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
        seg[idx].ans = seg[seg[idx].l].ans;
        seg[idx].mini = seg[seg[idx].l].mini;
        return;
    }
    seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
    seg[idx].mini = seg[seg[idx].l].mini;
}

void lazy_u(int idx, int x, int y, int z){
    if(idx==-1) return;
    if(seg[idx].lazy!=0){
        if(seg[idx].l!=-1){
            seg[seg[idx].l].lazy += seg[idx].lazy;
            seg[seg[idx].l].mini += seg[idx].lazy;
        }
        if(seg[idx].r!=-1){
            seg[seg[idx].r].lazy += seg[idx].lazy;
            seg[seg[idx].r].mini += seg[idx].lazy;
        }
        seg[idx].lazy = 0;
    }
    if(seg[idx].s>=x && seg[idx].e<=y){
        seg[idx].mini+=z;
        seg[idx].lazy+=z;   return;
    }
    if(seg[idx].e<x || seg[idx].s>y)    return;
    lazy_u(seg[idx].l, x, y, z);
    lazy_u(seg[idx].r, x, y, z);
    if(seg[idx].l==-1 && seg[idx].r==-1)    return;
    if(seg[idx].l==-1){
        seg[idx].ans = seg[seg[idx].r].ans;
        seg[idx].mini = seg[seg[idx].r].mini;
        return;
    }
    if(seg[idx].r==-1){
        seg[idx].ans = seg[seg[idx].l].ans;
        seg[idx].mini = seg[seg[idx].l].mini;
        return;
    }
    if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
        seg[idx].ans = seg[seg[idx].r].ans;
        seg[idx].mini = seg[seg[idx].r].mini;
        return;
    }
    if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
        seg[idx].ans = seg[seg[idx].l].ans;
        seg[idx].mini = seg[seg[idx].l].mini;
        return;
    }
    seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
    seg[idx].mini = seg[seg[idx].l].mini;
}

vector<int> sq;
int dx[4]={-1, -1, 0, 0}, dy[4]={0, -1, 0, -1};

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    seg[0]={0, 0, H*W, H*W, 0, 0, H*W-1, -1, -1};
    init(0);
    N=H*W;
    h=H; w=W;
    arr.resize(H);
    for(int i=0; i<H; i++){
        arr[i].resize(W);
    }
    for(int i=0; i<R.size(); i++){
        v.push_back({R[i], C[i]});
        arr[R[i]][C[i]]=i;
    }
    for(int i=0; i<=H; i++){
        for(int j=0; j<=W; j++){
            while(!sq.empty())  sq.pop_back();
            for(int k=0; k<4; k++){
                if(i+dx[k]>=0 && i+dx[k]<H && j+dy[k]>=0 && j+dy[k]<W){
                    sq.push_back(arr[i+dx[k]][j+dy[k]]);
                }
            }
            sort(sq.begin(), sq.end());
            for(int k=0; k<sq.size(); k++){
                if(k==0 || k==2){
                    lazy_u(0, sq[k], N, 1);
                }else{
                    lazy_u(0, sq[k], N, -1);
                }
            }
        }
    }
}

int swap_seats(int a, int b) {
    for(int i=v[a].x; i<=v[a].x+1; i++){
        for(int j=v[a].y; j<=v[a].y+1; j++){
            while(!sq.empty())  sq.pop_back();
            for(int k=0; k<4; k++){
                if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
                    sq.push_back(arr[i+dx[k]][j+dy[k]]);
                }
            }
            sort(sq.begin(), sq.end());
            for(int k=0; k<sq.size(); k++){
                if(k==0 || k==2){
                    lazy_u(0, sq[k], N, -1);
                }else{
                    lazy_u(0, sq[k], N, 1);
                }
            }
        }
    }
    for(int i=v[b].x; i<=v[b].x+1; i++){
        for(int j=v[b].y; j<=v[b].y+1; j++){
            while(!sq.empty())  sq.pop_back();
            for(int k=0; k<4; k++){
                if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
                    sq.push_back(arr[i+dx[k]][j+dy[k]]);
                }
            }
            sort(sq.begin(), sq.end());
            for(int k=0; k<sq.size(); k++){
                if(k==0 || k==2){
                    lazy_u(0, sq[k], N, -1);
                }else{
                    lazy_u(0, sq[k], N, 1);
                }
            }
        }
    }
    S tmp = v[a]; v[a] = v[b]; v[b] = tmp;
    arr[v[a].x][v[a].y]=a;  arr[v[b].x][v[b].y]=b;
    for(int i=v[a].x; i<=v[a].x+1; i++){
        for(int j=v[a].y; j<=v[a].y+1; j++){
            while(!sq.empty())  sq.pop_back();
            for(int k=0; k<4; k++){
                if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
                    sq.push_back(arr[i+dx[k]][j+dy[k]]);
                }
            }
            sort(sq.begin(), sq.end());
            for(int k=0; k<sq.size(); k++){
                if(k==0 || k==2){
                    lazy_u(0, sq[k], N, 1);
                }else{
                    lazy_u(0, sq[k], N, -1);
                }
            }
        }
    }
    for(int i=v[b].x; i<=v[b].x+1; i++){
        for(int j=v[b].y; j<=v[b].y+1; j++){
            while(!sq.empty())  sq.pop_back();
            for(int k=0; k<4; k++){
                if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
                    sq.push_back(arr[i+dx[k]][j+dy[k]]);
                }
            }
            sort(sq.begin(), sq.end());
            for(int k=0; k<sq.size(); k++){
                if(k==0 || k==2){
                    lazy_u(0, sq[k], N, 1);
                }else{
                    lazy_u(0, sq[k], N, -1);
                }
            }
        }
    }
    return seg[0].ans;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<R.size(); i++){
                  ~^~~~~~~~~
seats.cpp:170:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:191:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~
seats.cpp:209:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~
seats.cpp:229:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~
seats.cpp:247:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~

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