Submission #957395

#	Time	Username	Problem	Language	Result	Execution time	Memory
957395		YassirSalama	Two Currencies (JOI23_currencies)	C++17	30 / 100	1892 ms	76280 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
int BIT[MAXN];
int BIT2[MAXN];
void init(){
    // for(int i=0;i<MAXN;i++) BIT[i]=0;
    memset(BIT,0,sizeof(BIT));
    memset(BIT2,0,sizeof(BIT2));
}
void add(int i,int x){
    i++;
    while(i<MAXN){
        BIT[i]+=x;
        i+=i&-i;
    }
}
void add2(int i,int x){
    i++;
    while(i<MAXN){
        BIT[i]+=x;
        BIT2[i]++;
        i+=i&-i;
    }
}
int s2(int i){
    i++;
    int ans=0;
    while(i){
        ans+=BIT2[i];
        i-=i&-i;
    }
    return ans;
}
int s(int i){
    i++;
    int ans=0;
    while(i){
        ans+=BIT[i];
        i-=i&-i;
    }
    return ans;
}
int q(int l,int r){
    if(l>r) return 0LL;
    if(l==0) return s(r);
    return s(r)-s(l-1);
}  
int q2(int l,int r){
    if(l>r) return 0LL;
    if(l==0) return s2(r);
    return s2(r)-s2(l-1);
}  
int pref1[MAXN];
int pref2[MAXN];

signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m,Q;
cin>>n>>m>>Q;
vector<pair<int,int>> edges;
for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    edges.pb({a,b});
}
vector<tuple<int,int,int>> ed;
ed.pb({0,0,0});
for(int i=0;i<m;i++){
    int p,c;
    cin>>p>>c;
    p--;
    auto [a,b]=edges[p];
    ed.pb({c,a,b});
}
sort(all(ed));
auto up = [&](int i,int x){
    i++;
    pref1[i]+=x;
    pref2[i]++;
};
auto s1=[&](int l,int r){
    l++,r++;
    if(l>r) return 0LL;
    if(l==0) return pref1[r];
    return pref1[r]-pref1[l-1];
};
auto ss2 = [&](int l,int r){
    l++,r++;
    if(l>r) return 0LL;
    if(l==0) return pref2[r];
    else return pref2[r]-pref2[l-1];
};
for(int i=0;i<=m;i++){
    auto [c,a,b]=ed[i];
    up(a,c);
}
for(int i=1;i<MAXN;i++){
    pref1[i]+=pref1[i-1];
    pref2[i]+=pref2[i-1];
}
vector<vector<int>> queries;
for(int i=0;i<Q;i++){
    int s,t,x,y;
    cin>>s>>t>>x>>y;
    if(s>t) swap(s,t);
    queries.pb({m/2,0,m,s,t,x,y,i});
}
vector<vector<int>> cc=queries;
int ans[Q];
memset(ans,0,sizeof(ans));
while(true){
    init();
    vector<vector<int>> cp=queries;
    sort(all(queries));
    vector<vector<int>> ndone;
    for(auto x:queries){
        if(x[1]>x[2]) {
            continue;
        }
        else ndone.pb(x);
    }
    queries=ndone;
    if(queries.empty()) break;
    sort(all(queries));
    vector<vector<int>> c[m+1];
    for(auto x:queries){
        c[x[0]].pb(x);
    }
    for(int i=0;i<=m;i++){
        auto [d,a,b]=ed[i];
        add(a,d);
        for(auto x:c[i]){
            int a=x[3],b=x[4];
            int f=q(a,b-1);
            if(f<=x[6]){
                ans[x[7]]=i;
                cp[x[7]][1]=i+1;
                cp[x[7]][0]=(cp[x[7]][1]+cp[x[7]][2])/2;
            }else{
                cp[x[7]][2]=i-1;
                cp[x[7]][0]=(cp[x[7]][1]+cp[x[7]][2])/2;                
            }
        }
    }
    queries=cp;
}
queries=cc;
vector<vector<int>> c[m+1];
for(auto x:queries){
    c[ans[x[7]]].pb(x);
}
int dans[Q+1];
memset(dans,0,sizeof(dans));
init();
for(int i=0;i<=m;i++){
    auto [d,a,b]=ed[i];
    add2(a,d);
    for(auto t:c[i]){
        int a=t[3],b=t[4];
        int e=q2(a,b-1); 
        int x=t[5],y=t[6],j=t[7];
        int ee=ss2(a,b-1);
        ee-=e;
        if(x>=ee){
            dans[j]=x-ee;
        }else dans[j]=-1;
    }

}
for(int i=0;i<Q;i++){
    cout<<dans[i]<<endl;
}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:179:20: warning: unused variable 'y' [-Wunused-variable]
  179 |         int x=t[5],y=t[6],j=t[7];
      |                    ^
currencies.cpp:99:6: warning: variable 's1' set but not used [-Wunused-but-set-variable]
   99 | auto s1=[&](int l,int r){
      |      ^~

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