Submission #49158

#	Time	Username	Problem	Language	Result	Execution time	Memory
49158		ainta	New Home (APIO18_new_home)	C++17	57 / 100	5025 ms	289024 KiB

new_home

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define N_ 301000
#define SZ 524288
#define pii pair<int,int>
using namespace std;
int n, Q, K, X[N_];
const int INF = 1e9;
struct Store {
    int x, col, b, e;
}w[N_];
vector<int>G[N_];
struct Query {
    int x, t, num;
    bool operator<(const Query &p)const {
        return t < p.t;
    }
}P[N_];
int TT[N_];
struct Seg {
    int b, e, t;
    bool operator<(const Seg &p)const {
        return b != p.b ? b < p.b : e < p.e;
    }
};
struct AA {
    int x, t, ck;
    bool operator <(const AA &p)const {
        return t != p.t ? t<p.t : ck>p.ck;
    }
}U[N_ * 2];
 
struct Order {
    int x, num;
    bool operator<(const Order &p)const {
        return x < p.x;
    }
}ord[N_];
 
int TX[N_];
 
set<Seg>SS;
 
int RN;
struct PP {
    int ck, t, b, e, flag, x, num;
    bool operator<(const PP &p)const {
        return t < p.t;
    }
}R[15010000];
int RC;
 
pii Range(int b, int e) {
    int bb = lower_bound(X + 1, X + Q + 1, b) - X;
    int ee = lower_bound(X + 1, X + Q + 1, e + 1) - X - 1;
    return { bb,ee };
}
 
struct RR {
    int b, e;
    bool operator<(const RR &p)const {
        return b < p.b;
    }
};
vector<RR>VV;
 
void Add(int ck, int t1, int t2, int b, int e, int x) {
    if (x > 8e8 || x < -8e8)return;
    RN++;
    R[RC++] = { ck,t1,b,e,1,x, RN};
    R[RC++] = { ck,t2 + 1,b,e,-1,x, RN};
    VV.push_back({ t1,t2 });
}
 
void Make2(int t1, int t2, int x1, int x2) {
    x1 = ord[x1].x, x2 = ord[x2].x;
    if (x1 > x2 || t1 > t2)return;
    int mid = (x1 + x2) / 2;
    pii tp = Range(x1, mid);
    if (tp.first <= tp.second) {
        Add(0, t1, t2, tp.first, tp.second, x1);
    }
    tp = Range(mid + 1, x2);
    if (tp.first <= tp.second) {
        Add(1, t1, t2, tp.first, tp.second, x2);
    }
}
void Put(int x, int t) {
    auto it = SS.lower_bound({ x,0,0 });
    it--;
    int bb = it->b, ee = it->e;
    Make2((it->t), t - 1, bb, ee);
    SS.erase(it);
    SS.insert({ bb,x,t });
    SS.insert({ x, ee, t });
}
void Del(int x, int t) {
    auto it = SS.lower_bound({ x, -INF, 0 });
    int ee = it->e;
    Make2(it->t, t - 1, x, ee);
    auto it2 = it;
    it--;
    int bb = it->b;
    Make2(it->t, t - 1, bb, x);
    SS.erase(it);
    SS.erase(it2);
    SS.insert({ bb,ee,t });
}
int SSum[N_];
void Make(int col) {
    VV.clear();
    SS.clear();
    int cnt = 0;
    for (auto &t : G[col]) {
        ord[cnt++] = { w[t].x, t };
    }
    ord[cnt++] = { -INF, -1 };
    ord[cnt++] = { INF, -2 };
    sort(ord, ord + cnt);
    int i;
    for (i = 0; i < cnt; i++) {
        if (ord[i].num >= 0) {
            TX[ord[i].num] = i;
        }
    }
    SS.insert({ 0,cnt - 1,1 });
    int cc = 0;
    for (auto &t : G[col]) {
        U[cc++] = { TX[t], w[t].b, 1 };
        U[cc++] = { TX[t], w[t].e + 1, -1 };
    }
    sort(U, U + cc);
    for (i = 0; i < cc; i++) {
        if (U[i].ck == 1) {
            Put(U[i].x, U[i].t);
        }
        else {
            Del(U[i].x, U[i].t);
        }
    }
    auto it = SS.begin();
    Make2(it->t, Q, it->b, it->e);
    if (VV.empty())return;
    sort(VV.begin(), VV.end());
    int ee = -1, bb = -1;
    for (auto &x : VV) {
        if (ee < x.b) {
            if (ee != -1) {
                SSum[bb]++;
                SSum[ee + 1]--;
            }
            bb = x.b;
        }
        ee = max(ee, x.e);
    }
    SSum[bb]++, SSum[ee + 1]--;
}
int vv[7510000];
priority_queue<pii>PQ[SZ + SZ][2];
void Put2(int nd, int ck, int x, int num) {
    if (ck == 0) {
        PQ[nd][ck].push({ -x,num });
    }
    else {
        PQ[nd][ck].push({ x, num });
    }
}
void Put(int b, int e, int x, int ck, int num) {
    b += SZ, e += SZ;
    while(b<=e){
        if (b & 1) {
            Put2(b, ck, x, num);
        }
        if (!(e & 1)) {
            Put2(e, ck, x, num);
        }
        b = (b + 1) >> 1, e = (e - 1) >> 1;
    }
}
int Res[N_];
int Get(int x, int ox) {
    int nd = x + SZ, r = 0;
    while (nd) {
        while (!PQ[nd][0].empty()) {
            pii tp = PQ[nd][0].top();
            if (!vv[tp.second]) {
                r = max(r, ox + tp.first);
                break;
            }
            PQ[nd][0].pop();
        }
        while (!PQ[nd][1].empty()) {
            pii tp = PQ[nd][1].top();
            if (!vv[tp.second]) {
                r = max(r, tp.first - ox);
                break;
            }
            PQ[nd][1].pop();
        }
        nd >>= 1;
    }
    return r;
}
int main() {
    int i;
    scanf("%d%d%d", &n, &K, &Q);
    for (i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &w[i].x, &w[i].col, &w[i].b, &w[i].e);
        G[w[i].col].push_back(i);
    }
    for (i = 1; i <= Q; i++) {
        scanf("%d%d", &P[i].x, &P[i].t);
        TT[i] = P[i].t;
        X[i] = P[i].x;
        P[i].num = i;
    }
    sort(X + 1, X + Q + 1);
    sort(TT + 1, TT + Q + 1);
    for (i = 1; i <= n; i++) {
        w[i].b = lower_bound(TT + 1, TT + Q + 1, w[i].b) - TT;
        w[i].e = lower_bound(TT + 1, TT + Q + 1, w[i].e + 1) - TT - 1;
    }
    for (i = 1; i <= Q; i++) {
        P[i].t = lower_bound(TT + 1, TT + Q + 1, P[i].t) - TT;
    }
    for (i = 1; i <= K; i++) {
        Make(i);
    }
    sort(R, R + RC);
    sort(P + 1, P + Q + 1);
    int pv = 0;
    for (i = 1; i <= Q; i++)SSum[i] += SSum[i - 1];
    for (i = 1; i <= Q; i++) {
        while (pv < RC && R[pv].t <= P[i].t) {
            if (R[pv].flag == 1) {
                Put(R[pv].b, R[pv].e, R[pv].x, R[pv].ck, R[pv].num);
            }
            else {
                vv[R[pv].num] = 1;
            }
            pv++;
        }
        int x = lower_bound(X + 1, X + Q + 1, P[i].x) - X;
        Res[P[i].num] = Get(x, P[i].x);
        if (SSum[P[i].t] != K)Res[P[i].num] = 1e9;
    }
    for (i = 1; i <= Q; i++) {
        if (Res[i] > 3e8)printf("-1\n");
        else printf("%d\n", Res[i]);
    }
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:209:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:211:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &w[i].x, &w[i].col, &w[i].b, &w[i].e);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &P[i].x, &P[i].t);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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