Submission #220294

#	Time	Username	Problem	Language	Result	Execution time	Memory
220294		tictaccat	동기화 (JOI13_synchronization)	C++14	0 / 100	113 ms	14828 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;

int sz = 16;
vector<int> lzR(2*sz, -1), lzL(2*sz, 1e9), valsR(2*sz, -1), valsL(2*sz, 1e9);

void upd(int i, int l, int r, int x, int y, int valR, int valL) {
    if (y < x) return;
    valR = max(valR, lzR[i]);
    valL = min(valL, lzL[i]);
    if (x == l && y == r) {
        lzR[i] = max(lzR[i], valR);
        lzL[i] = min(lzL[i], valL);
        valsR[i] = max(valsR[i], valR);
        valsL[i] = min(valsL[i], valL);
        return;
    }
    int mid = (l+r)/2;
    upd(2*i, l, mid, x, min(y,mid), valR, valL);
    upd(2*i+1, mid+1, r, max(x,mid+1), y, valR, valL);
    valsR[i] = max(valsR[2*i], valsR[2*i+1]);
    valsL[i] = min(valsL[2*i], valsL[2*i+1]);
}

pair<int,int> query(int i, int l, int r, int x, int y) {
    if (y < x) return make_pair(-1,1e9);
    if (x == l && y == r) return make_pair(valsR[i],valsL[i]);
    int mid = (l+r)/2;
    auto q1 = query(2*i,l,mid, x, min(y,mid));
    auto q2 = query(2*i+1,mid+1,r, max(x,mid+1), y);
    int retR = max(q1.first, max(q2.first, lzR[i]));
    int retL = min(q1.second, min(q2.second, lzL[i]));
    return make_pair(retR, retL);
}

pair<int,int> query(int x, int y) {return query(1,0,sz-1,x,y);}
void upd(int x, int y, int valR, int valL) {upd(1,0,sz-1,x,y,valR,valL);}

int N,M,Q;
vector<vector<int>> adj(MAX);
vector<pair<int,int>> el;
vector<bool> active(MAX);
set<pair<int,int>> regions;

int main() {

    cin >> N >> M >> Q;

    for (int i = 0; i < N-1; i++) {
        int X,Y;
        cin >> X >> Y;
        X--; Y--;
        adj[X].push_back(Y);
        adj[Y].push_back(X);
        el.emplace_back(X,Y);
    }

    for (int i = 0; i < N; i++) {
        regions.insert(make_pair(i,i));
        upd(i,i,i,i);
        // r[i] = i;
        // l[i] = i;
    }

    for (int i = 0; i < M; i++) {
        int d;
        cin >> d;
        d--;
        active[d] = !active[d];
        int u,v;
        tie(u,v) = el[d];
        //if (u > v) swap(u,v);
        if (active[d]) {
          //  cout << "adding " << u << " " << v << "\n";
            auto cur1 = --regions.lower_bound(make_pair(u+1,-1));
            auto cur2 = --regions.lower_bound(make_pair(u+2,-1));
            int a = (*cur1).first;
            int b = (*cur2).second;
          //  cout << a << " " << b << "\n";
            regions.erase(cur1);
            regions.erase(cur2);
            regions.insert(make_pair(a,b));
            upd(a,b,query(b,b).first,query(a,a).second);
        }
        if (!active[d]) {
           // cout << "removing " << u << " " << v << "\n";
            auto cur = --regions.lower_bound(make_pair(u+1,-1));
            int a,b;
            tie(a,b) = *cur;
            regions.erase(cur);
            regions.insert(make_pair(a,u));
            regions.insert(make_pair(u+1,b));
          //  cout << a << " " << b << "\n";
        }
        //edge = el[d];
    }


    for (int q = 0; q < Q; q++) {
        int C; 
        cin >> C;
        C--;
        //cout << C << "\n";
        cout << query(C,C).first - query(C,C).second + 1 << "\n";
        //unique nodes for C
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40