Submission #1041312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041312		HorizonWest	Two Currencies (JOI23_currencies)	C++17	10 / 100	5083 ms	82512 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

struct LowerCommonAncestor
{
    vector <vector<int>> v;

    vector <int> L, E, H, lg; int idx, n;

    void dfs(int cur, int depth, int parent)
    {
        H[cur] = idx;
        E[idx] = cur;
        L[idx++] = depth;

        for (auto& u : v[cur]) if(u != parent)
        {
            dfs(u, depth + 1, cur);
            E[idx] = cur;
            L[idx++] = depth;
        }
    }

    vector <vector<int>> Spt;

    void RMQ()
    {
        Spt.assign(2 * n, vector <int>(log2(2 * n) + 1, 0));

        for (int i = 0; i < 2 * n; i++)
            Spt[i][0] = i;

        for (int j = 1; (1 << j) <= 2 * n; j++)
        {
            for (int i = 0; i + (1 << j) < 2 * n; i++)
                if (L[Spt[i][j - 1]] < L[Spt[i + (1 << (j - 1))][j - 1]])
                    Spt[i][j] = Spt[i][j - 1];
                else
                    Spt[i][j] = Spt[i + (1 << (j - 1))][j - 1];
        }
    }

    int Query(int i, int j)
    {
        if(i > j) swap(i, j); 
        int k = (int) lg[j-i+1]; 
        if (L[Spt[i][k]] <= L[Spt[j - (1 << k) + 1][k]])
            return Spt[i][k];
        else
            return Spt[j - (1 << k) + 1][k];
    }

    int Ancestor(int i, int j)
    {
        int a = min(H[i], H[j]), b = max(H[i], H[j]);
        return E[Query(a, b)];
    }

    LowerCommonAncestor(vector<vector<int>> &p, int lenght, int x)
    {
        n = lenght; idx = 1; v = p; 

        L.assign(2 * n, -1);
        E.assign(2 * n, -1);
        H.assign(2 * n, -1);
        lg.assign(2*n+1, 0); 
        _for(i, 2*n+1){
            lg[i] = floor(log((double) i) / log(2.0));
        }

        dfs(x, 0, 0); RMQ();
    }
};

int sqrt_n; 

struct SegmentTreeSum
{
    struct node
    {
        int val, cnt;

        node(int v = 0, int t = 0)
        {
            val = v; cnt = t; 
        }
    };

    vector <node> tree; int l;

    node merge(node a, node b)
    {
        return node(a.val + b.val, a.cnt + b.cnt);
    }

    void update(int k, int v)
    {
        k += (l - 1) + 1; tree[k] = node(v, (v != 0));
        for(k /= 2; k > 0; k /= 2)
            tree[k] = merge(tree[2*k], tree[2*k+1]);
    }

    node query(int k, int x, int y, int s, int e)
    {
        if(s > y || e < x)
            return node();
        if(s >= x && e <= y)
            return tree[k];

        int middle = (s + e) / 2;

        return merge(query(2*k, x, y, s, middle),
            query(2*k+1, x, y, middle + 1, e));
    }

    pair <int, int> query(int x, int y)
    {
        if(x > y) return { 0, 0 };  
        node ans = query(1, x+1, y+1, 1, l);
        return { ans.val, ans.cnt };
    }

    SegmentTreeSum(int n)
    {
        for(l = 1; l < n; (l <<= 1));
        tree.assign(2 * l, node());
    }
};

struct query
{
    int l, r, s, t, x, y, id; 

    bool operator < (const query &a) const {
        if(long(a.l/sqrt_n) == long(l/sqrt_n))
            return (long(a.l/sqrt_n) < long(l/sqrt_n));
        return a.r < r; 
    }

    query(int a, int b, int c, int d, int f, int g, int i){
        l = a; r = b; s = c; t = d; x = f; y = g; id = i; 
    }
};

vector <int> cmp(vector <int> &s)
{
    vector <pair<int, int>> t; 
    vector <int> ans(s.size()); 
    _for(i, s.size()){
        t.push_back({ s[i], i }); 
    }
    sort(all(t));
    _for(i, s.size()){
        ans[t[i].sd] = i; 
    }
    return ans; 
}

void solve()
{
    int n, m, q; cin >> n >> m >> q;

    sqrt_n = sqrt(n) + 1;

    vector <vector<int>> v(n+1, vector <int> ()),
        e(n+1, vector <int> ());  
    
    vector <int> f1(n+1), f2(n+1), s, cost(m);
    vector <pair<int, int>> edge; 
    
    _for(i, n-1)
    {
        int a, b; cin >> a >> b; 
        v[a].pb(b); v[b].pb(a); 
        edge.push_back({ a, b }); 
    }

    function <void(int, int)> dfs = [&](int node, int parent){
        f1[node] = s.size(); 
        s.push_back(node); 
        for(auto& u : v[node]) if(u != parent){
            dfs(u, node); 
        }
        f2[node] = s.size(); 
        s.push_back(node); 
    }; dfs(1, 0);

    _for(i, m) 
    {
        int p; cin >> p >> cost[i]; p--;
        if(f1[edge[p].fs] > f1[edge[p].sd])
            p = edge[p].fs; 
        else 
            p = edge[p].sd; 

        //cerr << p << " " << cost[i] << endl;
        e[p].push_back(i);  
    }

    vector <int> freq(n+1), pos = cmp(cost), ans(q); 

    vector <query> c;  LowerCommonAncestor Lc(v, n, 1); 

    //for(auto& u : s) cerr << u << " "; cerr << endl;

    _for(i, q)
    {
        int a, b, x, y; cin >> a >> b >> x >> y; 
        if(f1[a] > f1[b]) swap(a, b); 
        int lca = Lc.Ancestor(a, b);
        c.push_back(query((a == lca ? f1[a]+1 : f2[a]), f1[b], a, b, x, y, i)); 
    }

    int l = 0, r = -1, sum = 0;  sort(all(c)); 

    SegmentTreeSum St(m+3); 

    auto add = [&](int x){ 
        freq[x] = (freq[x] + 1) % 2; 
        for(auto& u : e[x])
        {
            if(freq[x] == 0){
                St.update(pos[u], 0); 
                sum--; 
            }else {
                St.update(pos[u], cost[u]); 
                sum++;
            }
        }
    }; 

    _for(i, q)
    {
        
        while (r < c[i].r){
            r++;  //cerr << i<< " " << r << " " << s[r] << " " << c[i].r << endl;
            add(s[r]); 
        }

        while (l > c[i].l){
            l--; 
            add(s[l]); 
        }

        while (r > c[i].r){
            add(s[r]);
            r--;  
        } 

        while (l < c[i].l){
            add(s[l]);
            l++; 
        }
        
       // cerr << "pas" << endl; 
        //continue;

        //cerr << c[i].s << " " << c[i].t << " " << lca << " " << sum << endl; 

        int a = -1, b = m+2; 

        while (abs(a - b) != 1)
        {
            int mid = (a + b) / 2; 

            if(St.query(0, mid).fs <= c[i].y)
                a = mid; 
            else 
                b = mid; 
        }
        
        pair <int, int> sx = St.query(0, a);   //cerr << c[i].l << " " << c[i].r  << " " << sum << " " << sx.fs << endl;

        ans[c[i].id] = max(-1LL, c[i].x - (sum - sx.sd));
    }

    for(auto& u : ans) cout << u << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'std::vector<long long int> cmp(std::vector<long long int>&)':
currencies.cpp:16:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define _for(i, n) for(int i = 0; i < (n); i++)
      |                                     ^
currencies.cpp:180:5: note: in expansion of macro '_for'
  180 |     _for(i, s.size()){
      |     ^~~~
currencies.cpp:16:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define _for(i, n) for(int i = 0; i < (n); i++)
      |                                     ^
currencies.cpp:184:5: note: in expansion of macro '_for'
  184 |     _for(i, s.size()){
      |     ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32