Submission #961352

#	Time	Username	Problem	Language	Result	Execution time	Memory
961352		MarwenElarbi	Two Currencies (JOI23_currencies)	C++17	10 / 100	5063 ms	33116 KiB

currencies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = (1LL << 61) - 1;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
vector<ii> cnt(nax);
int tin[nax];
vii adj[nax];
vi to[nax];
vi euler;
pair<ll,int> segtree[nax*4];
int timer=-1;
struct state{
    ll l,r,gold,silver,res;
};
vector<state> queries;
void euler_tour(int x,int p){
    tin[x]=euler.size();
    euler.pb(-1);
    for(auto u:adj[x]){
        if(u.fi==p) continue;
        euler.pb(u.se);
        euler_tour(u.fi,x);
        euler.pb(u.se);
    }
}
void update(int pos,int l,int r,int idx,int value){
    if(l==r){
        if(value){
            //cout <<"segtre"<<" "<<idx<<" "<<cnt[to[idx]].fi<<endl;
            //cout <<"add "<<idx<<endl;
            segtree[pos]={cnt[idx].fi,(cnt[idx].fi>0)};
        }
        else {
            //cout <<"remove "<<idx<<endl;
            segtree[pos]={0,0};
        }
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
    segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
    return;
}
int cur=0;
void query(int pos,int l,int r,ll value){
    if(l==r){
        return;
    }
    int mid=(r+l)/2;
    if(segtree[pos*2+1].fi>value) query(pos*2+1,l,mid,value);
    else {
        //cout <<l<<" "<<mid<<" "<<segtree[pos*2+1].fi<<" "<<value<<" nabba"<<endl;
        cur+=segtree[pos*2+1].se;
        value-=segtree[pos*2+1].fi;
        query(pos*2+2,mid+1,r,value);
    }
    return;
}
int main(){
    optimise;
    //setIO("dec");
    int n,m,q;
    cin>>n>>m>>q;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb({y,i});
        adj[y].pb({x,i});
    }
    euler_tour(0,-1);
    cnt.resize(m);
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;
        cnt[i]={y,x};
    }
    sort(cnt.begin(),cnt.end());
    for (int i = 0; i < m; ++i)
    {
        //cout <<cnt[i].fi<<" "<<cnt[i].se<<endl;
        to[cnt[i].se].pb(i);
    }
    for (int i = 0; i < q; ++i)
    {
        queries.emplace_back();
        cin>>queries[i].l>>queries[i].r>>queries[i].gold>>queries[i].silver;
        queries[i].l--;
        queries[i].r--;
        if(tin[queries[i].l]>tin[queries[i].r]) swap(queries[i].l,queries[i].r);
        queries[i].res=i;
    }
    int block_size = (int)sqrt(n);
    auto mo_cmp = [&](state a, state b) {
        int block_a = tin[a.l] / block_size;
        int block_b = tin[b.l] / block_size;
        if (block_a == block_b) { return tin[a.r] < tin[b.r]; }
        return block_a < block_b;
    };
    sort(queries.begin(), queries.end(), mo_cmp);
    int states=0;
    int count[4*nax];
    memset(count,0,sizeof count);
    auto remove = [&](int idx){
        //cout <<"remove "<<euler[idx]<<" "<<idx<<endl;
        for(auto u:to[euler[idx]]) update(0,0,m,u,0);
    };
    auto add = [&](int idx){
        //cout <<"add "<<euler[idx]<<" "<<idx<<endl;
        for(auto u:to[euler[idx]]) update(0,0,m,u,1);
    };
    int left=0;
    int right=-1;
    int ans[q];
    for (int i = 0; i < q; ++i)
    {
        int lefty=tin[queries[i].l];
        int righty=tin[queries[i].r];
        cur=0;
        //cout <<queries[i].l<<" "<<queries[i].r<<" "<<lefty<<" "<<righty<<endl;
        while(right<righty){
            right++;
            if(euler[right]==-1) continue;
            count[euler[right]]++;
            //cout <<idx<<endl;
            if(count[euler[right]]%2){
                //cout <<euler[idx]<<endl;
                states+=to[euler[right]].size();
                add(right);
            }else{
                states-=to[euler[right]].size();
                remove(right);
            }
        }
        while(right>righty){
            if(euler[right]!=-1){
                count[euler[right]]--;
                if(count[euler[right]]%2==1){
                    //cout <<euler[idx]<<endl;
                    states+=to[euler[right]].size();
                    add(right);
                }else{
                    states-=to[euler[right]].size();
                    remove(right);
                }       
            }
            right--;
        }
        while(left<lefty){
            if(euler[left]!=-1){
                //cout <<count[<<endl;
                count[euler[left]]--;
                if(count[euler[left]]%2==1){
                    //cout <<euler[left]<<endl;
                    states+=to[euler[left]].size();
                    add(left);
                }else{
                    states-=to[euler[left]].size();
                    remove(left);
                }       
            }
            left++;
        }
        while(left>lefty) {
            left--;
            if(euler[left]==-1) continue;
            count[euler[left]]++;
            //cout <<idx<<endl;
            if(count[euler[left]]%2){
                //cout <<euler[idx]<<endl;
                states+=to[euler[left]].size();
                add(left);
            }else{
                states-=to[euler[left]].size();
                remove(left);
            }
        }
        //cout <<"nabba"<<endl;
        query(0,0,m,queries[i].silver);
        //cout <<queries[i].gold<<" "<<states<<" "<<cur<<endl;
        ans[queries[i].res]=queries[i].gold-(states-cur);
    }
    for (int i = 0; i < q; ++i)
    {
        if(ans[i]<0) cout <<-1<<endl;
        else cout <<ans[i]<<endl;
    }
}

Compilation message (stderr)

currencies.cpp: In function 'void setIO(std::string)':
currencies.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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