提交记录 40171


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_dsh_260814 noi17f. 【NOI2017】分身术 Accepted 100 1.257 s 16716 KB C++ 19.38 KB
提交时间 评测时间
2026-08-17 21:22:41 2026-08-17 21:23:00
// NOI2017 分身术 — persistent SEGMENT TREE of x-monotone chains (upper/lower hulls).
// Rewrite of the persistent-treap pstfull13: each layer's x-sorted chain is a copy-on-write
// segment tree over the global x-order [0,SZ). Node = {ch0,ch1,first,last,cs} (24 bytes,
// deterministic: no prio/rotation/heap). split = PST path-copy; merge = segment-tree union of
// two disjoint x-ranges (O(log SZ)); tangent = direct O(log SZ) descent on the PST roots; the
// area cross-sum is the node field. Same onion+split/merge/bridge algorithm as pstfull13.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const int MAXN = 100005;
static const int MAXK = 130;
static const int PEEL = 105;
static const ll XMIN = -(1LL<<60), XMAX = (1LL<<60);

static struct Pt { ll x, y; } P[MAXN];
static int n, m;
static int SZ;                       // global x-order universe size [0,SZ)
static int gPos[MAXN];               // gPos[point] = global x-order position of point

static int K;
static vector<int> loV[MAXK], upV[MAXK];   // x-sorted, strictly-increasing-x chains
static vector<int> xLo[MAXK], xUp[MAXK];   // contiguous x-coords of the chains (for binary search)
static int loLen2[MAXK], upLen2[MAXK];
static int h[MAXK];
static int layer_of[MAXN];
static int gOrder[MAXN];
static int loIdxOf[MAXN], upIdxOf[MAXN];
static vector<int> delLo[MAXK], delUp[MAXK];
static int delMark[MAXN];
static int delStamp = 0;

static inline ll cross2(int a,int b){ return P[a].x*P[b].y-P[a].y*P[b].x; }
static inline ll crs3(int a,int b,int c){ return (P[b].x-P[a].x)*(P[c].y-P[b].y)-(P[b].y-P[a].y)*(P[c].x-P[b].x); }
static inline ll crsP(int o,int a,int b){ return (P[a].x-P[o].x)*(P[b].y-P[o].y)-(P[a].y-P[o].y)*(P[b].x-P[o].x); }

// ---- persistent segment tree (copy-on-write) over global x-order [0,SZ) ----
static const int NODE_MAX = 4000000;
static struct SN { int ch0, ch1; int first, last; ll cs; } sn[NODE_MAX];
static int tcnt = 1;
static int tcntBase = 0;

static inline int allocNode(int src){
    if(tcnt >= NODE_MAX){ fprintf(stderr,"NODE OVERFLOW %d\n", tcnt); exit(1); }
    int v = tcnt++;
    sn[v] = src ? sn[src] : SN{0,0,-1,-1,0};
    return v;
}
static inline void pull(int v){
    int l = sn[v].ch0, r = sn[v].ch1;
    sn[v].first = l ? sn[l].first : sn[r].first;
    sn[v].last  = r ? sn[r].last  : sn[l].last;
    ll s = 0;
    if(l) s += sn[l].cs;
    if(r) s += sn[r].cs;
    if(l && r) s += cross2(sn[l].last, sn[r].first);
    sn[v].cs = s;
}
// insert point p at global position posn (path-copy); used for build + newLeaf
static int insertLeaf(int u, int l, int r, int posn, int p){
    int v = allocNode(u);
    if(l == r){
        sn[v].ch0 = sn[v].ch1 = 0;
        sn[v].first = sn[v].last = p;
        sn[v].cs = 0;
        return v;
    }
    int mid = (l+r)>>1;
    if(posn <= mid) sn[v].ch0 = insertLeaf(sn[v].ch0, l, mid, posn, p);
    else            sn[v].ch1 = insertLeaf(sn[v].ch1, mid+1, r, posn, p);
    pull(v);
    return v;
}
static int newLeaf(int p){ return insertLeaf(0, 0, SZ-1, gPos[p], p); }
// bottom-up build of the sparse tree over sorted positions (shared prefixes, O(len) nodes
// instead of O(len log SZ)); pts[cnt] are point indices in increasing gPos order, all in [l,r].
static int buildRange(const int* pts, int cnt, int l, int r){
    if(cnt == 0) return 0;
    if(l == r){
        int v = allocNode(0);
        sn[v].ch0 = sn[v].ch1 = 0;
        sn[v].first = sn[v].last = pts[0];
        sn[v].cs = 0;
        return v;
    }
    int mid = (l+r)>>1;
    int lo = 0, hi = cnt-1, k = cnt;
    while(lo <= hi){
        int mm = (lo+hi)>>1;
        if(gPos[pts[mm]] > mid){ k = mm; hi = mm-1; } else lo = mm+1;
    }
    int L = buildRange(pts, k, l, mid);
    int R = buildRange(pts+k, cnt-k, mid+1, r);
    int v = allocNode(0);
    sn[v].ch0 = L; sn[v].ch1 = R;
    pull(v);
    return v;
}
static int buildTree(const vector<int>& pts, int len){
    if(!len) return 0;
    return buildRange(pts.data(), len, 0, SZ-1);
}
// extract the points of u (covering [l,r]) whose global position lies in [pL,pR],
// returning a copy-on-write tree covering the SAME [l,r] (shared subtrees reused).
static int clipRange(int u, int l, int r, int pL, int pR){
    if(!u) return 0;
    if(pR < l || r < pL) return 0;
    if(pL <= l && r <= pR) return u;
    int v = allocNode(u);
    int mid = (l+r)>>1;
    sn[v].ch0 = clipRange(sn[u].ch0, l, mid, pL, pR);
    sn[v].ch1 = clipRange(sn[u].ch1, mid+1, r, pL, pR);
    pull(v);
    return v;
}
// union-merge of two DISJOINT trees (a's positions < b's positions) -> O(log SZ)
static int mergeT(int a, int b){
    if(!a) return b;
    if(!b) return a;
    int v = allocNode(a);
    sn[v].ch0 = mergeT(sn[a].ch0, sn[b].ch0);
    sn[v].ch1 = mergeT(sn[a].ch1, sn[b].ch1);
    pull(v);
    return v;
}
static int clipByPos(int root, int pL, int pR){  // positions in [pL,pR]
    if(pL > pR || !root) return 0;
    return clipRange(root, 0, SZ-1, pL, pR);
}
static inline int clipByIndex(int root, const vector<int>& V, int l, int r){
    if(l > r) return 0;
    return clipByPos(root, gPos[V[l]], gPos[V[r]]);
}

// ---- point-to-chain tangents: direct O(log SZ) descent on the PST ----
// lower tangent from point oi (left of chain B) to B: first j with crsP(oi,B[j],B[j+1]) >= 0
static int lowerTangentJ(int oi, int rootB){
    int u = rootB;
    while(1){
        int L = sn[u].ch0, R = sn[u].ch1;
        if(!L && !R) return sn[u].first;
        if(!L){ u = R; continue; }
        if(!R){ u = L; continue; }
        if(crsP(oi, sn[L].last, sn[R].first) >= 0) u = L;
        else u = R;
    }
}
static int upperTangentJ(int oi, int rootB){
    int u = rootB;
    while(1){
        int L = sn[u].ch0, R = sn[u].ch1;
        if(!L && !R) return sn[u].first;
        if(!L){ u = R; continue; }
        if(!R){ u = L; continue; }
        if(crsP(oi, sn[L].last, sn[R].first) <= 0) u = L;
        else u = R;
    }
}
// reversed tangent from point P (right of chain A) to A
static int revTangentLower(int rootA, int P){
    int u = rootA;
    while(1){
        int L = sn[u].ch0, R = sn[u].ch1;
        if(!L && !R) return sn[u].first;
        if(!L){ u = R; continue; }
        if(!R){ u = L; continue; }
        if(crs3(sn[L].last, sn[R].first, P) < 0) u = L;
        else u = R;
    }
}
static int revTangentUpper(int rootA, int P){
    int u = rootA;
    while(1){
        int L = sn[u].ch0, R = sn[u].ch1;
        if(!L && !R) return sn[u].first;
        if(!L){ u = R; continue; }
        if(!R){ u = L; continue; }
        if(crs3(sn[L].last, sn[R].first, P) > 0) u = L;
        else u = R;
    }
}
// materialize chain points in x-order (fallback only)
static int collectPoints(int u, int* out){
    if(!u) return 0;
    int c = collectPoints(sn[u].ch0, out);
    if(!sn[u].ch0 && !sn[u].ch1){ out[c++] = sn[u].first; return c; }
    c += collectPoints(sn[u].ch1, out + c);
    return c;
}
static int lowerTangentArr(int oi, int* arr, int len){
    int lo = 0, hi = len-1, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)>>1;
        bool good = (mid == len-1) || (crsP(oi, arr[mid], arr[mid+1]) >= 0);
        if(good){ ans = mid; hi = mid-1; } else lo = mid+1;
    }
    return ans;
}

// common lower tangent (bridge): alternating fixpoint of the two point-to-chain tangents.
// Returns tangent POINTS i_out (on A), j_out (on B).
static void lowerBridge(int rootA, int rootB, int& i_out, int& j_out){
    if(sn[rootA].first == sn[rootA].last){ i_out = sn[rootA].first; j_out = lowerTangentJ(i_out, rootB); return; }
    if(sn[rootB].first == sn[rootB].last){ j_out = sn[rootB].first; i_out = revTangentLower(rootA, j_out); return; }
    int pa = sn[rootA].last;              // start from rightmost A
    int ci_pt = sn[rootA].last, cj_pt = sn[rootB].first;
    for(int it=0; it<64; it++){
        int pb = lowerTangentJ(pa, rootB);
        int pa_new = revTangentLower(rootA, pb);
        if(pa_new == ci_pt && pb == cj_pt){ i_out = pa_new; j_out = pb; return; }
        ci_pt = pa_new; cj_pt = pb;
        pa = pa_new;
    }
    // fallback (never reached in practice): materialize + binary search
    static int arrA[MAXN], arrB[MAXN];
    int pA = collectPoints(rootA, arrA);
    int pB = collectPoints(rootB, arrB);
    int lo = 0, hi = pA-1, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)>>1;
        int jj = lowerTangentArr(arrA[mid], arrB, pB);
        bool ok = (mid==0) || (crs3(arrA[mid-1], arrA[mid], arrB[jj]) > 0);
        if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
    }
    i_out = arrA[ans];
    j_out = arrB[lowerTangentArr(arrA[ans], arrB, pB)];
}
static void upperBridge(int rootA, int rootB, int& i_out, int& j_out){
    if(sn[rootA].first == sn[rootA].last){ i_out = sn[rootA].first; j_out = upperTangentJ(i_out, rootB); return; }
    if(sn[rootB].first == sn[rootB].last){ j_out = sn[rootB].first; i_out = revTangentUpper(rootA, j_out); return; }
    int pa = sn[rootA].last;
    int ci_pt = sn[rootA].last, cj_pt = sn[rootB].first;
    for(int it=0; it<64; it++){
        int pb = upperTangentJ(pa, rootB);
        int pa_new = revTangentUpper(rootA, pb);
        if(pa_new == ci_pt && pb == cj_pt){ i_out = pa_new; j_out = pb; return; }
        ci_pt = pa_new; cj_pt = pb;
        pa = pa_new;
    }
    // fallback
    static int arrA[MAXN], arrB[MAXN];
    int pA = collectPoints(rootA, arrA);
    int pB = collectPoints(rootB, arrB);
    int lo = 0, hi = pA-1, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)>>1;
        int jj = -1;
        { // upper tangent from arrA[mid] to B
            int ll=0, rr=pB-1, aa=0;
            while(ll<=rr){ int mm=(ll+rr)>>1; bool g=(mm==pB-1)||(crsP(arrA[mid],arrB[mm],arrB[mm+1])<=0); if(g){aa=mm;rr=mm-1;} else ll=mm+1; }
            jj = aa;
        }
        bool ok = (mid==0) || (crs3(arrA[mid-1], arrA[mid], arrB[jj]) < 0);
        if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
    }
    i_out = arrA[ans];
    { int ll=0, rr=pB-1, aa=0; while(ll<=rr){ int mm=(ll+rr)>>1; bool g=(mm==pB-1)||(crsP(arrA[ans],arrB[mm],arrB[mm+1])<=0); if(g){aa=mm;rr=mm-1;} else ll=mm+1; } j_out = arrB[aa]; }
}

// lower hull of A union B (A.x < B.x): trim at common tangent, concatenate
static int mergeChain(int rootA, int rootB){
    if(!rootA) return rootB;
    if(!rootB) return rootA;
    int i_pt, j_pt;
    lowerBridge(rootA, rootB, i_pt, j_pt);
    int Aleft = clipRange(rootA, 0, SZ-1, 0, gPos[i_pt]);       // A[0..i]
    int Bright = clipRange(rootB, 0, SZ-1, gPos[j_pt], SZ-1);   // B[j..]
    return mergeT(Aleft, Bright);
}
static int mergeChainUpper(int rootA, int rootB){
    if(!rootA) return rootB;
    if(!rootB) return rootA;
    int i_pt, j_pt;
    upperBridge(rootA, rootB, i_pt, j_pt);
    int Aleft = clipRange(rootA, 0, SZ-1, 0, gPos[i_pt]);       // A[0..i]
    int Bright = clipRange(rootB, 0, SZ-1, gPos[j_pt], SZ-1);   // B[j..]
    return mergeT(Aleft, Bright);
}

static int loRoot[MAXK], upRoot[MAXK];

static ll rd();
static void wl(ll v);

static void buildLayers(){
    static int order[MAXN];
    for(int i=0;i<n;i++) order[i]=i;
    sort(order, order+n, [](int a,int b){ return P[a].x!=P[b].x?P[a].x<P[b].x:P[a].y<P[b].y; });
    for(int i=0;i<n;i++){ gOrder[i]=order[i]; gPos[order[i]]=i; }
    static char alive[MAXN];
    for(int i=0;i<n;i++) alive[i]=1;
    static vector<int> lo, up;
    int rem = n; K = 0;
    for(int i=0;i<n;i++){ loIdxOf[i]=upIdxOf[i]=-1; layer_of[i]=-1; }
    while(rem >= 3 && K < PEEL){
        lo.clear();
        for(int t=0;t<n;t++){ if(!alive[t]) continue; int idx=order[t];
            while(lo.size()>=2 && crs3(lo[lo.size()-2],lo.back(),idx)<=0) lo.pop_back(); lo.push_back(idx); }
        up.clear();
        for(int t=n-1;t>=0;t--){ if(!alive[t]) continue; int idx=order[t];
            while(up.size()>=2 && crs3(up[up.size()-2],up.back(),idx)<=0) up.pop_back(); up.push_back(idx); }
        vector<int> H = lo;
        for(int t=1;t<(int)up.size()-1;t++) H.push_back(up[t]);
        if(H.size()<3) break;
        h[K] = (int)H.size();
        loV[K].clear();
        for(int t=0;t<(int)lo.size();t++) loV[K].push_back(lo[t]);
        if(loV[K].size()>=2 && P[loV[K].back()].x==P[loV[K][loV[K].size()-2]].x) loV[K].pop_back();
        upV[K].clear();
        for(int t=(int)up.size()-1;t>=0;t--) upV[K].push_back(up[t]);
        if(upV[K].size()>=2 && P[upV[K][0]].x==P[upV[K][1]].x) upV[K].erase(upV[K].begin());
        loLen2[K] = (int)loV[K].size(); upLen2[K] = (int)upV[K].size();
        for(int t=0;t<(int)loV[K].size();t++){ loIdxOf[loV[K][t]]=t; layer_of[loV[K][t]]=K; }
        for(int t=0;t<(int)upV[K].size();t++){ upIdxOf[upV[K][t]]=t; layer_of[upV[K][t]]=K; }
        for(int t=0;t<(int)H.size();t++) alive[gPos[H[t]]]=0;
        K++; rem -= H.size();
    }
    if(rem > 0){
        vector<int> rest;
        for(int t=0;t<n;t++){ if(alive[t]) rest.push_back(order[t]); }
        h[K] = (int)rest.size();
        loV[K] = rest; upV[K].clear();
        loLen2[K] = (int)rest.size(); upLen2[K] = 0;
        for(int t=0;t<(int)rest.size();t++){ loIdxOf[rest[t]]=t; layer_of[rest[t]]=K; }
        K++;
    }
    for(int d=0; d<K; d++){
        xLo[d].resize(loLen2[d]);
        for(int t=0;t<loLen2[d];t++) xLo[d][t]=(int)P[loV[d][t]].x;
        xUp[d].resize(upLen2[d]);
        for(int t=0;t<upLen2[d];t++) xUp[d][t]=(int)P[upV[d][t]].x;
    }
    // build persistent segment trees (loV is x-sorted; upV is x-sorted)
    for(int d=0; d<K; d++){
        loRoot[d] = buildTree(loV[d], loLen2[d]);
        upRoot[d] = buildTree(upV[d], upLen2[d]);
    }
    tcntBase = tcnt;
}

static inline int mergeEnv(int a, int b, int dir){
    return dir==+1 ? mergeChain(a,b) : mergeChainUpper(a,b);
}

// aligned chain traversal with early-stopping (same logic as pstfull13)
static int buildAligned(int d, int kind, int dir, ll xL, ll xR){
    if(d >= K) return 0;
    if(h[d] < 3){
        if(kind == 1) return 0;  // leftover has no upper chain
        int res = 0;
        for(int t=0;t<loLen2[d];t++){
            int p = loV[d][t];
            if(delMark[p]==delStamp) continue;
            if(P[p].x < xL || P[p].x > xR) continue;
            res = mergeT(res, newLeaf(p));
        }
        return res;
    }
    const vector<int>& V = (kind==0) ? loV[d] : upV[d];
    const vector<int>& XV = (kind==0) ? xLo[d] : xUp[d];
    const vector<int>& del = (kind==0) ? delLo[d] : delUp[d];
    int root = (kind==0) ? loRoot[d] : upRoot[d];
    int len = (int)V.size();
    int idxL = len, idxR = -1;
    { int lo=0, hi=len-1; while(lo<=hi){ int mid=(lo+hi)>>1; if(XV[mid]>=xL){ idxL=mid; hi=mid-1; } else lo=mid+1; } }
    { int lo=0, hi=len-1; while(lo<=hi){ int mid=(lo+hi)>>1; if(XV[mid]<=xR){ idxR=mid; lo=mid+1; } else hi=mid-1; } }
    if(idxL > idxR) return 0;
    int dl = (int)del.size();
    int di = 0;
    while(di < dl && del[di] < idxL) di++;
    if(di >= dl || del[di] > idxR){
        return clipByIndex(root, V, idxL, idxR);
    }
    int res = 0;
    int lastIncluded = idxL - 1;
    int i = di;
    while(i < dl){
        int a = del[i], b = a;
        while(i+1 < dl && del[i+1] == b+1){ b = del[++i]; }
        if(b < idxL){ i++; continue; }
        if(a > idxR) break;
        if(a-1 >= lastIncluded+1){
            int piece = clipByIndex(root, V, lastIncluded+1, a-1);
            res = mergeEnv(res, piece, dir);
        }
        ll xL_gap = (a > idxL) ? (ll)XV[a-1]+1 : xL;
        ll xR_gap = (b < idxR) ? (ll)XV[b+1]-1 : xR;
        if(xL_gap <= xR_gap){
            int sub = buildAligned(d+1, kind, dir, xL_gap, xR_gap);
            res = mergeEnv(res, sub, dir);
        }
        lastIncluded = b;
        i++;
    }
    if(lastIncluded+1 <= idxR){
        int piece = clipByIndex(root, V, lastIncluded+1, idxR);
        res = mergeEnv(res, piece, dir);
    }
    return res;
}

static int addExtremes(int res, int dir){
    int gl=-1, gr=-1;
    for(int i=0;i<n;i++) if(delMark[gOrder[i]]!=delStamp){ gl=gOrder[i]; break; }
    for(int i=n-1;i>=0;i--) if(delMark[gOrder[i]]!=delStamp){ gr=gOrder[i]; break; }
    if(gl>=0 && (!res || P[gl].x < P[sn[res].first].x)) res = mergeEnv(newLeaf(gl), res, dir);
    if(gr!=gl && (!res || P[gr].x > P[sn[res].last].x)) res = mergeEnv(res, newLeaf(gr), dir);
    return res;
}

static int buildLower(int d, ll xL, ll xR){
    int res = buildAligned(0, 0, +1, xL, xR);
    return addExtremes(res, +1);
}
static int buildUpper(int d, ll xL, ll xR){
    int res = buildAligned(0, 1, -1, xL, xR);
    return addExtremes(res, -1);
}

static ll solveQueries(){
    ll S = -1;
    ll ret = 0;
    for(int q=0;q<m;q++){
        tcnt = tcntBase;
        int k = (int)rd();
        delStamp++;
        for(int dd=0; dd<K; dd++){ delLo[dd].clear(); delUp[dd].clear(); }
        for(int j=0;j<k;j++){
            ll c = rd(); ll v = S+c; v %= n; if(v<0) v+=n;
            int id = (int)v;
            delMark[id] = delStamp;
            int d = layer_of[id];
            if(d >= 0){
                if(loIdxOf[id]>=0) delLo[d].push_back(loIdxOf[id]);
                if(upIdxOf[id]>=0) delUp[d].push_back(upIdxOf[id]);
            }
        }
        for(int dd=0; dd<K; dd++){
            if(delLo[dd].size()>1){ sort(delLo[dd].begin(), delLo[dd].end()); delLo[dd].erase(unique(delLo[dd].begin(),delLo[dd].end()), delLo[dd].end()); }
            if(delUp[dd].size()>1){ sort(delUp[dd].begin(), delUp[dd].end()); delUp[dd].erase(unique(delUp[dd].begin(),delUp[dd].end()), delUp[dd].end()); }
        }
        int loR = buildLower(0, XMIN, XMAX);
        int upR = buildUpper(0, XMIN, XMAX);
        ll loSum = loR ? sn[loR].cs : 0;
        ll upSum = upR ? sn[upR].cs : 0;
        int loFirst = loR ? sn[loR].first : -1;
        int loLast  = loR ? sn[loR].last  : -1;
        int upFirst = upR ? sn[upR].first : -1;
        int upLast  = upR ? sn[upR].last  : -1;
        ll ans = loSum - upSum;
        if(loFirst>=0 && upFirst>=0){
            ans += cross2(loLast, upLast) + cross2(upFirst, loFirst);
        }
        if(ans < 0) ans = -ans;
        S = ans;
        ret = ans;
        wl(ans);
    }
    return ret;
}

// ---- IO ----
#include <sys/auxv.h>
#include <stdint.h>
struct DuckInfo {
    uint64_t abi_version;
    const char *stdin_ptr; uint64_t stdin_size;
    char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
    char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
    const char *IB_ptr; uint64_t IB_limit;
    char *OB_ptr; uint64_t OB_limit;
    uint64_t tsc_frequency;
} __attribute__((packed));
static const char* ibuf; static size_t ipos=0, ilen=0;
static char* obuf; static size_t opos=0;
static DuckInfo* duck;
static char local_in[1<<25], local_out[1<<25];
static inline char gc(){ if(ipos>=ilen) return 0; return ibuf[ipos++]; }
static inline ll rd(){ char c; while((c=gc()) && (c<'0'||c>'9') && c!='-'); if(c==0) return 0; int s=1; if(c=='-'){s=-1;c=gc();} ll v=0; while(c>='0'&&c<='9'){v=v*10+(c-'0');c=gc();} return s*v; }
static inline void wl(ll v){ if(v==0){obuf[opos++]='0';obuf[opos++]='\n';return;} char t[32];int z=0; if(v<0){obuf[opos++]='-';v=-v;} while(v){t[z++]='0'+(v%10);v/=10;} while(z)obuf[opos++]=t[--z]; obuf[opos++]='\n'; }

int main(){
    duck=(DuckInfo*)getauxval(0x6b637564);
    if(duck && duck->stdin_ptr){
        ibuf=duck->stdin_ptr; ilen=duck->stdin_size; ipos=0;
        obuf=duck->stdout_ptr; opos=0;
    } else {
        ilen=fread(local_in,1,sizeof(local_in),stdin); ibuf=local_in; ipos=0;
        obuf=local_out; opos=0;
    }
    n=(int)rd(); m=(int)rd();
    for(int i=0;i<n;i++){ P[i].x=rd(); P[i].y=rd(); }
    SZ = 1; while(SZ < n) SZ <<= 1;
    buildLayers();
    solveQueries();
    if(duck && duck->stdin_ptr){
        duck->stdout_size=opos;
        asm volatile("mov $60,%%rax; xor %%edi,%%edi; syscall" ::: "rax","rdi","memory");
    } else {
        fwrite(obuf,1,opos,stdout);
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #160.58 us112 KBAcceptedScore: 5

Testcase #27.512 ms356 KBAcceptedScore: 5

Testcase #37.803 ms356 KBAcceptedScore: 5

Testcase #48.531 ms360 KBAcceptedScore: 5

Testcase #5231.488 ms8 MB + 468 KBAcceptedScore: 5

Testcase #6235.931 ms9 MB + 984 KBAcceptedScore: 5

Testcase #7235.931 ms9 MB + 984 KBAcceptedScore: 5

Testcase #8250.045 ms11 MB + 524 KBAcceptedScore: 5

Testcase #9333.07 ms8 MB + 648 KBAcceptedScore: 5

Testcase #10333.026 ms10 MB + 96 KBAcceptedScore: 5

Testcase #11414.592 ms8 MB + 768 KBAcceptedScore: 5

Testcase #12564.488 ms9 MB + 560 KBAcceptedScore: 5

Testcase #13583.098 ms10 MB + 716 KBAcceptedScore: 5

Testcase #14640.937 ms11 MB + 196 KBAcceptedScore: 5

Testcase #15930.347 ms16 MB + 304 KBAcceptedScore: 5

Testcase #161.246 s13 MB + 856 KBAcceptedScore: 5

Testcase #171.257 s14 MB + 484 KBAcceptedScore: 5

Testcase #181.179 s15 MB + 104 KBAcceptedScore: 5

Testcase #191.251 s15 MB + 716 KBAcceptedScore: 5

Testcase #201.199 s16 MB + 332 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2026-09-03 16:45:36 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠