Submission #365503

#	Time	Username	Problem	Language	Result	Execution time	Memory
365503		doowey	New Home (APIO18_new_home)	C++14	100 / 100	3500 ms	381344 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 5;
const int inf = (int)1e9;
map<int, int> cnt[N];
int x[N], t[N], a[N], b[N];

vector<int> cors;

struct lin{
    int tim;
    int lef;
    int rig;
    int mode;
};

int cur;

vector<lin> lis;


const int M = (int)2e6 + 10;
map<int, int> low[M];
map<int, int> high[M];

int segt[M * 2][2];
int m;

int getid(int pp){
    return lower_bound(cors.begin(), cors.end(), pp) - cors.begin();
}

void segm(int li, int ri, int mod){
    lis.push_back({cur, li, ri, mod});
    cors.push_back((li + ri) / 2);
}

void setv(int id, int q, int vl){
    id += m;
    segt[id][q] = vl;
    id /= 2;
    while(id > 0){
        if(q == 0) segt[id][q] = max(segt[id*2][q], segt[id*2+1][q]);
        else segt[id][q] = min(segt[id*2][q], segt[id*2+1][q]);
        id /= 2;
    }
}

int get(int li, int ri, int q){
    li += m;
    ri += m;
    int ret = 0;
    if(q == 0) ret = -inf;
    else ret = inf;
    while(li <= ri){
        if(li % 2 == 1){
            if(q == 0) ret = max(ret, segt[li][0]);
            else ret = min(ret, segt[li][1]);
            li ++ ;
        }
        if(ri % 2 == 0){
            if(q == 0) ret = max(ret, segt[ri][0]);
            else ret = min(ret, segt[ri][1]);
            ri -- ;
        }
        li /= 2;
        ri /= 2;
    }
    return ret;
}

int fin_p(int pp){
    int ix = getid(pp);
    return max(pp - get(ix, m - 1, 1), get(0, ix, 0) - pp);
}

void add_line(lin nw){
    int li = nw.lef;
    int ri = nw.rig;
    int vv = nw.mode;
    int mid = (li + ri) / 2;
    int mi = getid(mid);
    if(nw.mode == 0){
        low[mi][li] ++ ;
        high[mi][ri] ++ ;
    }
    else{
        low[mi][li] -- ;
        if(low[mi][li] == 0)
            low[mi].erase(li);
        high[mi][ri] -- ;
        if(high[mi][ri] == 0)
            high[mi].erase(ri);
    }
    int lw = inf;
    int rw = -inf;
    if(!low[mi].empty()){
        auto it = low[mi].begin();
        lw = min(lw, it->fi);
    }
    if(!high[mi].empty()){
        auto it = high[mi].end();
        it -- ;
        rw = max(rw, it->fi);
    }
    setv(mi, 1, lw);
    setv(mi, 0, rw);
}

void add(int typ, int v){
    cnt[typ][v] ++ ;
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;
    segm(pv->fi, nx->fi, 1);
    segm(pv->fi, it->fi, 0);
    segm(it->fi, nx->fi, 0);
}

void del(int typ, int v){
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;

    segm(pv->fi, it->fi, 1);
    segm(it->fi, nx->fi, 1);
    segm(pv->fi, nx->fi, 0);
    cnt[typ][v] -- ;
    if(cnt[typ][v] == 0){
        cnt[typ].erase(v);
    }
}

int xx[N];
int yr[N];

int soln[N];

int main(){
    fastIO;
    int n, k, q;
    cin >> n >> k >> q;
    vector<pii> eve;
    for(int i = 1; i <= n; i ++ ){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        x[i] *= 2;
        cors.push_back(x[i]);
        eve.push_back(mp(a[i], i));
        eve.push_back(mp(b[i] + 1, i));
    }
    vector<pii> ord;
    for(int i = 1; i <= q; i ++ ){
        cin >> xx[i] >> yr[i];
        xx[i] *= 2;
        cors.push_back(xx[i]);
        ord.push_back(mp(yr[i], i));
    }
    sort(ord.begin(), ord.end());
    sort(eve.begin(), eve.end());
    for(int i = 1; i <= k ; i ++ ){
        cnt[i][-inf] ++ ;
        cnt[i][inf] ++ ;
        segm(-inf, inf, 0);
    }
    for(int i = 0 ; i < eve.size(); i ++ ){
        cur = eve[i].fi;
        if(cur == a[eve[i].se]){
            add(t[eve[i].se], x[eve[i].se]);
        }
        else{
            del(t[eve[i].se], x[eve[i].se]);
        }
    }
    sort(cors.begin(), cors.end());
    cors.resize(unique(cors.begin(), cors.end()) - cors.begin());
    m = cors.size();
    for(int i = 0 ; i < m * 2; i ++ ){
        segt[i][0]=-inf;
        segt[i][1]=inf;
    }
    int it = 0;
    int vv;
    for(auto e : ord){
        while(it < lis.size() && lis[it].tim <= e.fi){
            add_line(lis[it]);
            it ++ ;
        }
        vv = fin_p(xx[e.se]);
        vv /= 2;
        if(vv > (int)1e8)
            soln[e.se] = -1;
        else
            soln[e.se] = vv;
    }
    for(int i = 1; i <= q; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void add_line(lin)':
new_home.cpp:90:9: warning: unused variable 'vv' [-Wunused-variable]
   90 |     int vv = nw.mode;
      |         ^~
new_home.cpp: In function 'int main()':
new_home.cpp:183:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int i = 0 ; i < eve.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
new_home.cpp:202:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lin>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         while(it < lis.size() && lis[it].tim <= e.fi){
      |               ~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20