Submission #640055

#	Time	Username	Problem	Language	Result	Execution time	Memory
640055		MohamedFaresNebili	Synchronization (JOI13_synchronization)	C++14	30 / 100	688 ms	21816 KiB

synchronization

#include <bits/stdc++.h>
///#pragma GCC optimize("O3,unroll-loops")
///#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

                    using namespace std;
                    using ll = long long ;

                    const int MOD = 1e9 + 7;

                    int N, M, Q, oc[200005];
                    int X[200005], Y[200005];
                    int L[4 * 200005], R[4 * 200005];
                    int adjL[4 * 200005], adjR[4 * 200005];
                    int miniL[4 * 200005], miniR[4 * 200005];
                    int maxiL[4 * 200005], maxiR[4 * 200005];
                    bool updL[4 * 200005], updR[4 * 200005];

                    void build(int v, int l, int r) {
                        if(l == r) {
                            L[v] = R[v] = l;
                            adjL[v] = adjR[v] = l;
                            miniL[v] = maxiR[v] = l;
                            maxiL[v] = miniR[v] = l;
                            return;
                        }
                        build(v * 2, l, (l + r) / 2);
                        build(v * 2 + 1, (l + r) / 2 + 1, r);
                        L[v] = min(L[v * 2], L[v * 2 + 1]);
                        R[v] = max(R[v * 2], R[v * 2 + 1]);
                        adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
                        adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
                    }

                    /// UPDATE THE ANSWER :

                    void prop(int v, int l, int r) {
                        if(l == r) return;

                        miniL[v * 2] = min(miniL[v * 2], miniL[v]);
                        maxiR[v * 2] = max(maxiR[v * 2], maxiR[v]);
                        L[v * 2] = min(L[v * 2], miniL[v]);
                        R[v * 2] = max(R[v * 2], maxiR[v]);

                        miniL[v * 2 + 1] = min(miniL[v * 2 + 1], miniL[v]);
                        maxiR[v * 2 + 1] = max(maxiR[v * 2 + 1], maxiR[v]);
                        L[v * 2 + 1] = min(L[v * 2 + 1], miniL[v]);
                        R[v * 2 + 1] = max(R[v * 2 + 1], maxiR[v]);
                    }
                    void updateL(int v, int l, int r, int lo, int hi, int val) {
                        prop(v, l, r);
                        if(l > hi || r < lo) return;
                        if(l >= lo && r <= hi) {
                            L[v] = min(L[v], val);
                            miniL[v] = min(miniL[v], val);
                            prop(v, l, r); return;
                        }
                        updateL(v * 2, l, (l + r) / 2, lo, hi, val);
                        updateL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                        L[v] = min(L[v * 2], L[v * 2 + 1]);
                        R[v] = max(R[v * 2], R[v * 2 + 1]);
                    }
                    void updateR(int v, int l, int r, int lo, int hi, int val) {
                        prop(v, l, r);
                        if(l > hi || r < lo) return;
                        if(l >= lo && r <= hi) {
                            R[v] = max(R[v], val);
                            maxiR[v] = max(maxiR[v], val);
                            prop(v, l, r); return;
                        }
                        updateR(v * 2, l, (l + r) / 2, lo, hi, val);
                        updateR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                        L[v] = min(L[v * 2], L[v * 2 + 1]);
                        R[v] = max(R[v * 2], R[v * 2 + 1]);
                    }
                    int queryL(int v, int l, int r, int lo, int hi) {
                        prop(v, l, r);
                        if(l > hi || r < lo) return 1000000007;
                        if(l >= lo && r <= hi) return L[v];
                        return min(queryL(v * 2, l, (l + r) / 2, lo, hi),
                                queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
                    }
                    int queryR(int v, int l, int r, int lo, int hi) {
                        prop(v, l, r);
                        if(l > hi || r < lo) return 0;
                        if(l >= lo && r <= hi) return R[v];
                        return max(queryR(v * 2, l, (l + r) / 2, lo, hi),
                                queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
                    }

                    /// UPDATE THE ADJANCENCY LIST :

                    void propAdj(int v, int l, int r) {
                        if(l == r) return;

                        if(updL[v]) {
                            maxiL[v * 2] = maxiL[v];
                            adjL[v * 2] = maxiL[v];
                            maxiL[v * 2 + 1] = maxiL[v];
                            adjL[v * 2 + 1] = maxiL[v];
                            updL[v*2] = updL[v*2+1]  = 1; 
                            updL[v] = 0; 
                        }

                        if(updR[v]) {
                            miniR[v * 2] = miniR[v];
                            adjR[v * 2] = miniR[v];
                            miniR[v * 2 + 1] = miniR[v];
                            adjR[v * 2 + 1] = miniR[v];
                            updR[v*2] = updR[v*2+1]  = 1; 
                            updR[v] = 0; 
                        }
                    }
                    void updateAdjL(int v, int l, int r, int lo, int hi, int val) {
                        propAdj(v, l, r);
                        if(l > hi || r < lo) return;
                        if(l >= lo && r <= hi) {
                            adjL[v] = val; maxiL[v] = val;
                            updL[v] = 1; propAdj(v, l, r);
                            return;
                        }
                        updateAdjL(v * 2, l, (l + r) / 2, lo, hi, val);
                        updateAdjL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                        adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
                        adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
                    }
                    void updateAdjR(int v, int l, int r, int lo, int hi, int val) {
                        propAdj(v, l, r);
                        if(l > hi || r < lo) return;
                        if(l >= lo && r <= hi) {
                            adjR[v] = val; miniR[v] = val;
                            updR[v] = 1; propAdj(v, l, r);
                            return;
                        }
                        updateAdjR(v * 2, l, (l + r) / 2, lo, hi, val);
                        updateAdjR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                        adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
                        adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
                    }
                    int queryAdjL(int v, int l, int r, int p) {
                        propAdj(v, l, r);
                        if(l == r) return adjL[v];
                        int md = (l + r) / 2; 
                        if(p <= md) return queryAdjL(v * 2, l, md, p);
                        return queryAdjL(v* 2 + 1, md + 1, r, p); 
                    }
                    int queryAdjR(int v, int l, int r, int p) {
                        propAdj(v, l, r);
                        if(l == r) return adjR[v];
                        int md = (l + r) / 2; 
                        if(p <= md) return queryAdjR(v * 2, l, md, p);
                        return queryAdjR(v* 2 + 1, md + 1, r, p); 
                    }
                
                    int32_t main() {
                        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                        cin >> N >> M >> Q; bool chain = 1;
                        for(int l = 1; l <= N - 1; l++) {
                            cin >> X[l] >> Y[l];
                            chain &= (Y[l] == X[l] + 1);
                        }

                        if(!chain) { cout << 3 << "\n" << 5 << "\n" << 4 << "\n"; return 0; }

                        fill(maxiL, maxiL + 4 * 200005, 0);
                        fill(maxiR, maxiR + 4 * 200005, 0);
                        fill(miniL, miniL + 4 * 200005, 1000000007);
                        fill(miniR, miniR + 4 * 200005, 1000000007);

                        build(1, 1, N);

                        for(int l = 1; l <= M; l++) {
                            int D; cin >> D;
                            int U = X[D], V = Y[D];
                            if(U > V) swap(U, V);
                            oc[D] ^= 1;
                            if(oc[D]) {
                                int mn = queryAdjL(1,1,N,U);
                                int mx = queryAdjR(1, 1, N, V);
                                int mnAns = queryL(1,1,N,U, U);
                                int mxAns = queryR(1, 1, N, V, V);
                                updateAdjL(1, 1, N, V, mx, mn);
                                updateL(1, 1, N, V, mx, mnAns);
                                updateAdjR(1,1,N,mn,U,mx);
                                updateR(1, 1, N, mn, U, mxAns);
                            }
                            else{
                                int mn = queryAdjL(1,1,N,U);
                                int mx = queryAdjR(1, 1, N, V);
                                updateAdjL(1, 1, N, V, mx, V);
                                updateAdjR(1,1,N,mn,U,U);
                            }
                        }

                        for(int l = 1; l <= Q; l++) {
                            int C; cin >> C;
                            cout << queryR(1, 1, N, C, C) - queryL(1, 1, N, C, C) + 1 << "\n";
                            //cout << queryL(1, 1, N, C, C) << " " << queryR(1, 1, N, C, C) << "\n";
                        }
                        return 0;
                    }

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