Submission #1091114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091114		ThylOne	Meteors (POI11_met)	C++14	100 / 100	1222 ms	44540 KiB

met

    //####################
    //Meteors
    //####################
    #include<bits/stdc++.h>
     
    using namespace std;
    using ll = long long;
    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define rall(x) x.begin(), x.end()
    int nbState,nbPlanet;
    const int maxiState = 300000;
    int attempt[maxiState];
    vector<int> representant[maxiState];
    int nbMeteor;
    const int maxiMeteor = 300000;
    struct meteor{
        int l,r;
        ll a;
    };
    meteor meteors[maxiMeteor];
    #define LSONE(x) (x&(-x))
    struct fenwick{
        vector<ll> val;
        fenwick(int n){
            val.resize(n+2);
            fill(all(val),0);
        }
        void update(int pos, ll v){
            while(pos<val.size()){
                val[pos] += v;
                pos += LSONE(pos);
            }
        }
        ll rsq(int i){
            ll re = 0;
            while(i){
                re += val[i];
                i -= LSONE(i);
            }
            return re;
        }
        ll rsq(int i,int j){
            return rsq(j) - rsq(i - 1);
        }
        void ruq(int i,int j, ll a){
            update(i, a);
            update(j+1,-a);
        }
    };
    int mid(pair<int,int> a){
        return (a.first+a.second)/2;
    }
    void solve(){
        pair<int,int> ranges[nbState];
        fill(ranges,ranges+nbState,make_pair(1,nbMeteor+1));
        const int LOG = 20;
        for(int l = 0; l < LOG; l++){
            vector<int> req[nbMeteor+2];
            for(int i=0;i<nbState;i++){
                if(ranges[i].first!=ranges[i].second)
                    req[mid(ranges[i])].pb(i);
            }
            fenwick ft(nbPlanet);
            for(int t = 1; t<= nbMeteor; t++){
                meteor &met = meteors[t - 1];
                //application de la météorite
                if(met.l<=met.r){
                    ft.ruq(met.l,met.r,met.a);
                }else{
                    ft.ruq(1,met.r,met.a);
                    ft.ruq(met.l,nbPlanet,met.a);
                }
     
                for(int r:req[t]){
                    
                    ll tot = 0;
                    for(int repr:representant[r]){
                      tot+=ft.rsq(repr);
                      if(tot>=attempt[r])break;
                    }
                    if(tot>=attempt[r]){
                        ranges[r].second=mid(ranges[r]);
                    }else{
                        ranges[r].first = mid(ranges[r])+1;
                    }
                }
            }
        }
        for(int i = 0; i < nbState ; i++){
            if(ranges[i].first!=ranges[i].second){
                cerr<<"errror system merde..."<<endl;
            }else{
                cout<<(ranges[i].second==nbMeteor+1?"NIE":to_string(ranges[i].second))<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>nbState>>nbPlanet;
        for(int i = 0; i<nbPlanet;i++){
            int v;cin>>v;
            v--;
            representant[v].pb(i+1);
        }
        for(int i= 0;i<nbState;i++)
            cin>>attempt[i];
     
        cin>>nbMeteor;
        for(int i = 0; i< nbMeteor ; i++){
            cin>>meteors[i].l>>meteors[i].r>>meteors[i].a;
        }
        solve();
     
        return 0;
    };

Compilation message (stderr)

met.cpp: In member function 'void fenwick::update(int, ll)':
met.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(pos<val.size()){
      |                   ~~~^~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13