Submission #895520

#	Time	Username	Problem	Language	Result	Execution time	Memory
895520		Aiperiii	Two Currencies (JOI23_currencies)	C++14	0 / 100	6 ms	10840 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e5+5;
vector <int> c[N];
int ind_val[N];
pair <int,int> t[N*4];
void update(int v,int tl,int tr,int pos,int x){
    if(tl==tr){
        t[v].ff+=(ind_val[pos]*x);
        t[v].ss+=x;
    }
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)update(v*2,tl,tm,pos,x);
        else update(v*2+1,tm+1,tr,pos,x);
        t[v].ff=t[v*2].ff+t[v*2+1].ff;
        t[v].ss=t[v*2].ss+t[v*2+1].ss;
    }
}
void get(int v,int tl,int tr,int& SUM,int& NUM){
    if(t[v].ff<=SUM){
        SUM-=t[v].ff;
        NUM+=t[v].ss;
        return;
    }
    if(tl==tr){
        int d=SUM/ind_val[v];
        NUM+=d;SUM=0;
        return;
    }
    int tm=(tl+tr)/2;
    if(t[v*2].ff<=SUM){
        get(v*2,tl,tm,SUM,NUM);
        get(v*2+1,tm+1,tr,SUM,NUM);
    }
    else get(v*2,tl,tm,SUM,NUM);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
    }
    set <int> st;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        c[x].pb(y);
        st.insert(y);
    }
    int indx=1;
    map <int,int> val_ind;
    for(auto x : st){
        ind_val[indx]=x;
        val_ind[x]=indx;
        indx++;
    }
    
    vector <vector <int> > v;
    vector <int> ans(q);
    for(int i=0;i<q;i++){
        int l,r,x,y;
        cin>>l>>r>>x>>y;
        if(l>r)swap(l,r);
        v.pb({l,r,i,x,y});
    }
    sort(all(v));
    
    int k=sqrt(n);
    int cnt=1;
    vector < vector < vector <int>  >  > g;
    g.pb({});
    for(int i=0;i<v.size();i++){
        int newgr=0;
        while(v[i][0]>k*cnt){
            cnt++;
            newgr=1;
        }
        if(newgr)g.pb({});
        g[g.size()-1].pb(v[i]);
        
    }
    
    for(int i=0;i<g.size();i++){
        if(g[i].size()==0)continue;
        for(int j=0;j<g[i].size();j++){
            swap(g[i][j][0],g[i][j][1]);
        }
        
        sort(all(g[i]));
        
        int l=g[i][0][1];
        int r=g[i][0][0];
        int ind=g[i][0][2];
        int x=g[i][0][3];
        int y=g[i][0][4];
        for(int k=l;k<r;k++){
            for(auto d : c[k]){
                update(1,1,st.size(),val_ind[d],1);
            }
        }
       int  NUM=0,SUM=y;
       // cout<<l<<" "<<r<<"\n";
        get(1,1,st.size(),SUM,NUM);
        //cout<<"\n";
        int left=t[1].ss-NUM;
        if(left>x)ans[ind]=-1;
        else ans[ind]=x-left;
        
        for(int j=1;j<g[i].size();j++){
            
            l=g[i][j][1];
            r=g[i][j][0];
            ind=g[i][j][2];
            x=g[i][j][3];
            y=g[i][j][4];
            
            for(int k=g[i][j-1][0];k<r;k++){
                for(auto d : c[k]){
                    update(1,1,st.size(),val_ind[d],1);
                }
            }
            if(l<g[i][j-1][1]){
                for(int k=l;k<g[i][j-1][1];k++){
                    for(auto d : c[k]){
                        update(1,1,st.size(),val_ind[d],1);
                    }
                }
            }
            else if(l>g[i][j-1][1]){
                for(int k=g[i][j-1][1];k<l;k++){
                    for(auto d : c[k]){
                        update(1,1,st.size(),val_ind[d],-1);
                    }
                }
            }
            NUM=0;SUM=y;
            //cout<<l<<" "<<r<<"\n";
            get(1,1,st.size(),SUM,NUM);
            //cout<<"\n";
            int left=t[1].ss-NUM;
            if(left>x)ans[ind]=-1;
            else ans[ind]=x-left;
            
        }
        
        for(int j=1;j<=st.size()*4;j++){
            t[j].ff=0;t[j].ss=0;
        }
    }
    
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
 

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:81:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
currencies.cpp:92:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<g.size();i++){
      |                 ~^~~~~~~~~
currencies.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j=0;j<g[i].size();j++){
      |                     ~^~~~~~~~~~~~
currencies.cpp:118:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j=1;j<g[i].size();j++){
      |                     ~^~~~~~~~~~~~
currencies.cpp:155:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(int j=1;j<=st.size()*4;j++){
      |                     ~^~~~~~~~~~~~~

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