Submission #91800

#	Time	Username	Problem	Language	Result	Execution time	Memory
91800		Retro3014	Seats (IOI18_seats)	C++17	100 / 100	3687 ms	182040 KiB

seats

#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
#include <map>
 
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 lazy;
    int 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;
 
int tp=1;
 
void init(int x){
    if(seg[x].s!=seg[x].e){
        if(seg[x].l==-1){
            seg[x].l=tp;
            seg[tp]={0, (seg[x].s+seg[x].e)/2-seg[x].s+1, 0, seg[x].s, (seg[x].s+seg[x].e)/2, -1, -1};
            tp++;
            init(tp-1);
        }
        if(seg[x].r==-1){
            seg[x].r=tp;
            seg[tp]={0, seg[x].e-(seg[x].s+seg[x].e)/2, 0, (seg[x].s+seg[x].e)/2+1, seg[x].e, -1, -1};
            tp++;
            init(tp-1);
        }
    }
}
 
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};
map<int, int> mp;
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    seg[0]={0, H*W, 0, 0, H*W-1, -1, -1};
    seg.resize(2*H*W);
    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);
                    mp[sq[k]]++;
                }else{
                    mp[sq[k]]--;
                    //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){
                    mp[sq[k]]-=1;
                }else{
                    mp[sq[k]]+=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){
                    mp[sq[k]]-=1;
                    //lazy_u(0, sq[k], N, -1);
                }else{
                    mp[sq[k]]+=1;
                    //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){
                    mp[sq[k]]+=1;
                    //lazy_u(0, sq[k], N, 1);
                }else{
                    mp[sq[k]]-=1;
                    //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){
                    mp[sq[k]]+=1;
                    //lazy_u(0, sq[k], N, 1);
                }else{
                    mp[sq[k]]-=1;
                    //lazy_u(0, sq[k], N, -1);
                }
            }
        }
    }
    for(map<int, int>::iterator it = mp.begin(); it!=mp.end(); it = mp.begin()){
        if(it->second !=0)  lazy_u(0, it->first, N, it->second);
        mp.erase(it);
    }
    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:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<R.size(); i++){
                  ~^~~~~~~~~
seats.cpp:165: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:189:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<sq.size(); k++){
                          ~^~~~~~~~~~
seats.cpp:207: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:249: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: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30