oj.uz

Submission #603363

# Submission time Handle Problem Language Result Execution time Memory
603363 2022-07-24T05:26:30 Z 반딧불(#8427) Synchronization (JOI13_synchronization) C++17
30 / 100
 368 ms 24776 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int x, y, idx;
    Edge(){}
    Edge(int x, int y, int idx): x(x), y(y), idx(idx){}
};

struct Pair{
    int min, max;
    Pair(){}
    Pair(int min, int max): min(min), max(max){}

    Pair operator+(const Pair &r)const{
        return Pair(::min(min, r.min), ::max(max, r.max));
    }
};

struct segTree{
    Pair tree[400002], lazy[400002];

    void init(int i, int l, int r){
        lazy[i] = Pair(1e9, 0);
        if(l==r){
            tree[i] = Pair(l, l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void propagate(int i, int l, int r){
        tree[i] = tree[i] + lazy[i];
        if(l!=r) lazy[i*2] = lazy[i*2] + lazy[i], lazy[i*2+1] = lazy[i*2+1] + lazy[i];
        lazy[i] = Pair(1e9, 0);
    }

    void update(int i, int l, int r, int s, int e, Pair p){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = p;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, p);
        update(i*2+1, m+1, r, s, e, p);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Pair query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return Pair(1e9, 0);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} tree;

int n, m, q;
int ex[100002], ey[100002];
vector<Edge> link[100002];
int arr[200002];
int query[100002];
vector<int> toggle[100002];

bool on[100002];
int ans[100002];
set<int> st;

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<n; i++){
        scanf("%d %d", &ex[i], &ey[i]);
        link[ex[i]].push_back(Edge(ex[i], ey[i], i));
        link[ey[i]].push_back(Edge(ey[i], ex[i], i));
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &arr[i]);
        toggle[arr[i]].push_back(i);
    }
    for(int i=1; i<=q; i++) scanf("%d", &query[i]);

    for(int i=0; i<=n; i++) st.insert(i);

    tree.init(1, 1, n);
    for(int i=1; i<=m; i++){
        if(on[arr[i]]){
            on[arr[i]] = 0;
            st.insert(arr[i]);
            continue;
        }
        int x = arr[i];
        auto it = st.lower_bound(x);
        int l = *prev(it)+1, r = *next(it);
        st.erase(x);
        on[x] = 1;
        Pair tmp = tree.query(1, 1, n, l, r);
        tree.update(1, 1, n, l, r, tmp);
    }

    for(int i=1; i<=q; i++){
        Pair tmp = tree.query(1, 1, n, query[i], query[i]);
        printf("%d\n", tmp.max - tmp.min + 1);
    }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d", &ex[i], &ey[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:89:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     for(int i=1; i<=q; i++) scanf("%d", &query[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 4 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 22640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5016 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Correct 28 ms 6988 KB Output is correct
8 Correct 339 ms 24772 KB Output is correct
9 Correct 368 ms 24776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 21908 KB Output is correct
2 Correct 268 ms 24424 KB Output is correct
3 Correct 263 ms 24544 KB Output is correct
4 Correct 298 ms 24600 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -