oj.uz

Submission #417971

# Submission time Handle Problem Language Result Execution time Memory
417971 2021-06-04T17:29:16 Z ACmachine The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 3000 ms 75400 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FOR(i, n, 0, 1)
#define pb push_back
#define ff first
#define ss second
vector<int> h;
const int INF = (int)2e9 + 15;
struct segtree{
    vector<vector<array<int, 2>>> tree;
    vector<int> lch, rch;
    int n;
    int create_new(){
        tree.pb(vector<array<int, 2>>());
        lch.pb(-1); rch.pb(-1);
        return (int)tree.size() - 1;
    }
    segtree(){}
    segtree(int sz){
        n = 1;
        while(n < sz) n *= 2;
        create_new();
    }
    void upd(int l, int r, array<int, 2> val){upd0(l, r, 0, n, 0, val);}
    void upd0(int l, int r, int beg, int end, int v, array<int, 2> val){
        if(beg >= l && end <= r){
            tree[v].pb(val);
            return;
        }
        if(beg >= r || end <= l) 
            return;
        int mid = (beg + end) >> 1;
        if(lch[v] == -1 && !(beg >= r || mid <= l)){
            int id = create_new();
            lch[v] = id;
            upd0(l, r, beg, mid, lch[v], val);
        }
        else if(!(beg >= r || mid <= l)){
            upd0(l, r, beg, mid, lch[v], val);
        }
        if(rch[v] == -1 && !(mid >= r || end <= l)){
            int id = create_new();
            rch[v] = id;
            upd0(l, r, mid, end, rch[v], val);
        }
        else if(!(mid >= r || end <= l)){
            upd0(l, r, mid, end, rch[v], val);
        }
    }
    void query0(int pos, int beg, int end, int v, vector<int> &res, int val){
        if(beg > pos || end <= pos)
            return;
        array<int, 2> ts = {val, -INF};
        int id = lower_bound(tree[v].begin(), tree[v].end(), ts) - tree[v].begin();
        FOR(i, id, tree[v].size(), 1){
            if(tree[v][i][0] != val) 
                break;
            res.pb(h[tree[v][i][1]]);
        }
        if(beg == pos && end == pos + 1) 
            return;
        int mid = (beg + end) >> 1;
        if(lch[v] != -1)
            query0(pos, beg, mid, lch[v], res, val);
        if(rch[v] != -1)
            query0(pos, mid, end, rch[v], res, val);
    }
};
segtree st;
int n;

void init(int N, int d, int H[]) {
    n = N;
    REP(i, N) 
        h.pb(H[i]);
}

void curseChanges(int U, int A[], int B[]) {
    st = segtree(U + 5);
    map<array<int, 2>, int> edges;
    FOR(i, 1, U + 1, 1){
        array<int, 2> tm = {A[i - 1], B[i - 1]};
        if(tm[0] > tm[1]) swap(tm[0], tm[1]);
        if(edges.find(tm) != edges.end()){
            st.upd(edges[tm], i, tm);
            edges.erase(tm);
        }
        else{
            edges[tm] = i;
        }
    }
    for(auto x : edges){
        auto tm = x.ff;
        st.upd(x.ss, U + 1, tm); 
    }
    REP(i, st.tree.size()){
        int up = st.tree[i].size();
        REP(j, up){
            auto x = st.tree[i][j];
            swap(x[0], x[1]);
            st.tree[i].pb(x);
        }
        sort(st.tree[i].begin(), st.tree[i].end());
    }
}

int question(int x, int y, int v) {
    vector<int> f;
    vector<int> s;
    st.query0(v, 0, st.n, 0, f, x);
    st.query0(v, 0, st.n, 0, s, y);
    if(f.empty() || s.empty()){
        return (int)1e9;
    } 
    sort(f.begin(), f.end());
    sort(s.begin(), s.end());
    int ans = (int)1e9 + 5;
    for(int x : f){
        int id = lower_bound(s.begin(), s.end(), x) - s.begin();
        if(id > 0){
            ans = min(ans, abs(x - s[id - 1]));
        }
        if(id < (int)s.size()){
            ans = min(ans, abs(x - s[id]));
        }
    }
    return ans;
}

Compilation message

potion.cpp: In member function 'void segtree::query0(int, int, int, int, std::vector<int>&, int)':
potion.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
potion.cpp:58:9: note: in expansion of macro 'FOR'
   58 |         FOR(i, id, tree[v].size(), 1){
      |         ^~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
potion.cpp:5:19: note: in expansion of macro 'FOR'
    5 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
potion.cpp:99:5: note: in expansion of macro 'REP'
   99 |     REP(i, st.tree.size()){
      |     ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 584 KB Output is correct
2 Correct 4 ms 584 KB Output is correct
3 Correct 5 ms 584 KB Output is correct
4 Correct 18 ms 1324 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 73252 KB Output is correct
2 Correct 1006 ms 73248 KB Output is correct
3 Correct 415 ms 34972 KB Output is correct
4 Correct 2061 ms 64832 KB Output is correct
5 Correct 1261 ms 73708 KB Output is correct
6 Execution timed out 3098 ms 57124 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 73276 KB Output is correct
2 Correct 1386 ms 39268 KB Output is correct
3 Correct 1488 ms 57372 KB Output is correct
4 Correct 1860 ms 57148 KB Output is correct
5 Correct 1414 ms 75400 KB Output is correct
6 Correct 2003 ms 57144 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 3624 KB Output is correct
2 Correct 165 ms 2180 KB Output is correct
3 Correct 190 ms 1796 KB Output is correct
4 Correct 898 ms 3136 KB Output is correct
5 Correct 877 ms 3324 KB Output is correct
6 Correct 211 ms 3512 KB Output is correct
7 Correct 680 ms 2256 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 4 ms 584 KB Output is correct
3 Correct 4 ms 584 KB Output is correct
4 Correct 5 ms 584 KB Output is correct
5 Correct 18 ms 1324 KB Output is correct
6 Correct 1104 ms 73252 KB Output is correct
7 Correct 1006 ms 73248 KB Output is correct
8 Correct 415 ms 34972 KB Output is correct
9 Correct 2061 ms 64832 KB Output is correct
10 Correct 1261 ms 73708 KB Output is correct
11 Execution timed out 3098 ms 57124 KB Time limit exceeded
12 Halted 0 ms 0 KB -