oj.uz

Submission #1110805

# Submission time Handle Problem Language Result Execution time Memory
1110805 2024-11-10T14:14:54 Z koukirocks The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 339 ms 262144 KB 
#include <bits/stdc++.h>
namespace {
    using namespace std;
}

struct Node {
    int l,r;
    multiset<int> h;
    vector<int> lz;
    Node *lft,*rt;
    Node(int _l,int _r,multiset<int> &ph):l(_l),r(_r),h(ph),lft(nullptr),rt(nullptr) {}
    void edit(int val) {
        if (h.find(val)==h.end()) h.insert(val);
        else h.erase(h.find(val));
    }
    void pd() {
        while (!lz.empty()) {
            int val=lz.back();
            if (lft) lft->edit(val);
            if (rt) rt->edit(val);
            lz.pop_back();
        }
    }
    void update(int L,int R,int val) {
        if (L<=l and r<=R) {
            lz.push_back(val);
            edit(val);
            return;
        }
        int mid=l+r>>1;
        pd();
        if (L<=mid) {
            if (!lft) lft=new Node(l,mid,h);
            lft->update(L,R,val);
        }
        if (mid<R) {
            if (!rt) rt = new Node(mid+1,r,h);
            rt->update(L,R,val);
        }
    }
    multiset<int>& query(int t) {
        if (l==r) return h;
        pd();
        int mid=l+r>>1;
        if (t<=mid) {
            if (lft) return lft->query(t);
            else return h;
        } else {
            if (rt) return rt->query(t);
            else return h;
        }
    }
};

namespace {
    vector<Node*> seg;
    int n,d,u;
    vector<int> h;
}

void init(int N, int D, int H[]) {
    n=N;d=D;
    h.resize(n);
    for (int i=0;i<n;i++) h[i]=H[i];
}

void curseChanges(int U, int A[], int B[]) {
    u=U;
    seg.resize(n,nullptr);
    multiset<int> emp;
    for (int i=0;i<n;i++) seg[i] = new Node(1,u,emp);
    for (int i=0;i<u;i++) {
        seg[A[i]]->update(i+1,u,h[B[i]]);
        seg[B[i]]->update(i+1,u,h[A[i]]);
    }
}

int question(int x, int y, int v) {
    multiset<int> &a = seg[x]->query(v);
    multiset<int> &b = seg[y]->query(v);
    // for (int i:a) cout<<i<<" ";
    // cout<<"a\n";
    // for (int i:b) cout<<i<<" ";
    // cout<<"b\n"<<flush;
    int ans=1e9;
    for (int i:a) {
        auto ptr = b.lower_bound(i);
        if (ptr!=b.end()) ans=min(ans,abs(*ptr-i));
        if (ptr!=b.begin()) ans=min(ans,abs(*prev(ptr)-i));
    }
    return ans;
}


/*
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0 
0 5 5 1000000000
3 0 11 14
*/

Compilation message

potion.cpp: In member function 'void Node::update(int, int, int)':
potion.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid=l+r>>1;
      |                 ~^~
potion.cpp: In member function 'std::multiset<int>& Node::query(int)':
potion.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4688 KB Output is correct
2 Correct 6 ms 4688 KB Output is correct
3 Correct 5 ms 4528 KB Output is correct
4 Correct 24 ms 16632 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 335 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 339 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 62024 KB Output is correct
2 Correct 188 ms 84768 KB Output is correct
3 Correct 176 ms 46168 KB Output is correct
4 Runtime error 311 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 5 ms 4688 KB Output is correct
3 Correct 6 ms 4688 KB Output is correct
4 Correct 5 ms 4528 KB Output is correct
5 Correct 24 ms 16632 KB Output is correct
6 Runtime error 335 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -