oj.uz

Submission #1091113

# Submission time Handle Problem Language Result Execution time Memory
1091113 2024-09-19T20:46:29 Z ThylOne Meteors (POI11_met) C++14
74 / 100
 896 ms 27916 KB 
    //####################
    //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]){
                        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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7768 KB Output is correct
2 Correct 3 ms 7948 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7576 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10668 KB Output is correct
2 Correct 108 ms 11408 KB Output is correct
3 Correct 79 ms 11200 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10948 KB Output is correct
2 Correct 80 ms 10988 KB Output is correct
3 Correct 103 ms 11496 KB Output is correct
4 Correct 20 ms 9424 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10708 KB Output is correct
2 Correct 74 ms 11624 KB Output is correct
3 Correct 40 ms 9816 KB Output is correct
4 Correct 74 ms 11384 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10588 KB Output is correct
2 Correct 95 ms 10952 KB Output is correct
3 Correct 56 ms 10616 KB Output is correct
4 Correct 92 ms 11712 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 27916 KB Output is correct
2 Incorrect 671 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 27704 KB Output is correct
2 Incorrect 648 ms 22684 KB Output isn't correct
3 Halted 0 ms 0 KB -