Submission #1110812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110812		koukirocks	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	645 ms	262144 KiB

potion

#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 Node {
    int l,r;
    vector<int> lz;
    Node *lft,*rt;
    Node(int _l,int _r):l(_l),r(_r),lft(nullptr),rt(nullptr) {}
    void update(int L,int R,int val) {
        if (L<=l and r<=R) {
            lz.push_back(val);
            return;
        }
        int mid=l+r>>1;
        if (L<=mid) {
            if (!lft) lft=new Node(l,mid);
            lft->update(L,R,val);
        }
        if (mid<R) {
            if (!rt) rt = new Node(mid+1,r);
            rt->update(L,R,val);
        }
    }
    void query(int t,vector<int> &h) {
        for (int i:lz) h.push_back(i);
        int mid=l+r>>1;
        if (t<=mid) {
            if (lft) return lft->query(t,h);
        } else {
            if (rt) return rt->query(t,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);
    for (int i=0;i<n;i++) seg[i] = new Node(1,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]]);
            seg[B[i]]->update(tm[pair(A[i],B[i])],i,h[A[i]]);
            // cout<<A[i]<<" "<<B[i]<<" "<<tm[pair(A[i],B[i])]<<" "<<i<<" a b tm i\n";
            tm[pair(A[i],B[i])]=0;
        }
    }
    for (auto [p,t]:tm) {
        if (t==0) continue;
        seg[p.F]->update(t,u,h[p.S]);
        seg[p.S]->update(t,u,h[p.F]);
    }
}

int question(int x, int y, int v) {
    vector<int> a,b;
    seg[x]->query(v,a);
    seg[y]->query(v,b);
    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 (stderr)

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

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30