oj.uz

Submission #1110931

# Submission time Handle Problem Language Result Execution time Memory
1110931 2024-11-11T03:07:06 Z koukirocks The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 1475 ms 262144 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
namespace {
    using namespace std;
}
typedef pair<int,int> pii;

struct SEG {
    struct Node {
        vector<int> lz;
        int lft,rt;
        Node():lft(0),rt(0) {}
    };
    int n;
    vector<Node> tree;
    SEG(int _n):n(_n) {
        tree.push_back(Node());
    }
    int add() {
        tree.push_back(Node());
        return tree.size()-1;
    }
    void update(int L,int R,int val,int l,int r,int id) {
        if (L<=l and r<=R) {
            tree[id].lz.push_back(val);
            return;
        }
        int mid=l+r>>1;
        if (L<=mid) {
            if (!tree[id].lft) tree[id].lft = add();
            update(L,R,val,l,mid,tree[id].lft);
        }
        if (mid<R) {
            if (!tree[id].rt) tree[id].rt = add();
            update(L,R,val,mid+1,r,tree[id].rt);
        }
    }
    void query(int t,vector<int> &h,int l,int r,int id) {
        for (int i:tree[id].lz) h.push_back(i);
        int mid=l+r>>1;
        if (t<=mid) {
            if (tree[id].lft) query(t,h,l,mid,tree[id].lft);
        } else {
            if (tree[id].rt) query(t,h,mid+1,r,tree[id].rt);
        }
    }
};

namespace {
    vector<SEG> seg;
    vector<vector<int>> lst;
    int n,d,u;
    vector<int> h;
    int *AA=nullptr,*BB=nullptr;
}

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

void curseChanges(int U, int A[], int B[]) {
    AA=A;BB=B;
    u=U;
    seg.resize(n,SEG(u));
    map<pii,int> tm;
    for (int i=0;i<u;i++) {
        if (A[i]>B[i]) swap(A[i],B[i]);
        if (tm[pair(A[i],B[i])]==0) tm[pair(A[i],B[i])]=i+1;
        else {
            seg[A[i]].update(tm[pair(A[i],B[i])],i,h[B[i]],1,u,0);
            seg[B[i]].update(tm[pair(A[i],B[i])],i,h[A[i]],1,u,0);
            tm[pair(A[i],B[i])]=0;
        }
    }
    for (auto [p,t]:tm) {
        if (t==0) continue;
        lst[p.F].push_back(t);
        lst[p.S].push_back(t);
    }
    for (int i=0;i<n;i++) {
        sort(all(lst[i]));
        // cout<<i<<" :\n";
        // for (auto [a,b]:lst[i]) cout<<a<<" "<<b<<"\n";
    }
}

int question(int x, int y, int v) {
    vector<int> a,b;
    seg[x].query(v,a,1,u,0);
    seg[y].query(v,b,1,u,0);
    // for (int i:a) cout<<i<<" ";
    // cout<<"a\n";
    // for (int i:b) cout<<i<<" ";
    // cout<<"b\n"<<flush;
    auto it = upper_bound(all(lst[x]),v);
    for (auto i=lst[x].begin();i!=it;i++) a.push_back((AA[*i-1]==x?h[BB[*i-1]]:h[AA[*i-1]]));
    it = upper_bound(all(lst[y]),v);
    for (auto i=lst[y].begin();i!=it;i++) b.push_back((AA[*i-1]==y?h[BB[*i-1]]:h[AA[*i-1]]));
    sort(all(a));
    sort(all(b));
    // 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 = lower_bound(all(b),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 SEG::update(int, int, int, int, int, int)':
potion.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid=l+r>>1;
      |                 ~^~
potion.cpp: In member function 'void SEG::query(int, std::vector<int>&, int, int, int)':
potion.cpp:42:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         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 3 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 21 ms 11520 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 29540 KB Output is correct
2 Correct 245 ms 29552 KB Output is correct
3 Correct 489 ms 155856 KB Output is correct
4 Correct 1475 ms 157392 KB Output is correct
5 Correct 430 ms 22596 KB Output is correct
6 Runtime error 623 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 29644 KB Output is correct
2 Correct 1229 ms 259068 KB Output is correct
3 Runtime error 705 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2384 KB Output is correct
2 Correct 104 ms 10560 KB Output is correct
3 Correct 110 ms 8160 KB Output is correct
4 Correct 619 ms 9224 KB Output is correct
5 Correct 634 ms 5092 KB Output is correct
6 Correct 83 ms 2128 KB Output is correct
7 Correct 469 ms 10808 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 21 ms 11520 KB Output is correct
6 Correct 284 ms 29540 KB Output is correct
7 Correct 245 ms 29552 KB Output is correct
8 Correct 489 ms 155856 KB Output is correct
9 Correct 1475 ms 157392 KB Output is correct
10 Correct 430 ms 22596 KB Output is correct
11 Runtime error 623 ms 262144 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -