Submission #411720

#	Time	Username	Problem	Language	Result	Execution time	Memory
411720		losmi247	Horses (IOI15_horses)	C++14	100 / 100	1464 ms	37704 KiB

horses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+23;
const int mod = 1000000007;

int n;
ll x[N],y[N];


ll dp[105][1005];
ll dajdp(){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= 1000; j++){
            dp[i][j] = -1;
        }
    }
    dp[0][1] = 0;
    for(int i = 1; i <= n; i++){  /// nakon kraja i-te godine
        for(ll j = 0; j <= 1000; j++){   /// imam j konja posle prodavanja
            int nagore = (j+x[i]-1)/x[i];
            nagore *= x[i];
            for(ll pre = nagore; pre <= 1000; pre += x[i]){   /// koliko sam konja imao pre prodavanja
                if(dp[i-1][pre/x[i]] != -1) dp[i][j] = max(dp[i][j],dp[i-1][pre/x[i]]+(pre-j)*y[i]);
            }
        }
    }

    return dp[n][0];
}


bool cmp(int i,int j){
    if(i == j) return 0;
    if(i < j){
        ll prod = y[j];
        for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
            if(x[h] >= (y[i]+prod-1)/prod) return 0;
            else prod *= x[h];
        }
        return 1;
    }
    else{
        ll prod = y[i];
        for(int h = j+1; h <= i; h++){
            if(x[h] >= (y[j]+prod-1)/prod) return 1;
            else prod *= x[h];
        }
        return 0;
    }
}

ll probaj(){
    vector <int> v;
    for(int i = 1; i <= n; i++) v.push_back(i);
    sort(v.begin(),v.end(),cmp);

    int pos = v[0];
    ll sol = 1;
    for(int i = 1; i <= pos; i++){
        sol *= x[i];
        sol %= mod;
    }
    sol *= y[pos];
    sol %= mod;

    return sol;
}


vector <ll> novx,novy;
bool cmp1(pair <int,int> a,pair <int,int> b){
    int i = a.first,j = b.first;
    if(i == j) return 0;
    if(i < j){
        ll prod = novy[j];
        for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
            if(novx[h] >= (novy[i]+prod-1)/prod) return 0;
            else prod *= novx[h];
        }
        return 1;
    }
    else{
        ll prod = novy[i];
        for(int h = j+1; h <= i; h++){
            if(novx[h] >= (novy[j]+prod-1)/prod) return 1;
            else prod *= novx[h];
        }
        return 0;
    }
}


int drvox[4*N],drvoy[4*N];

void build(int i,int j,int node){
    if(i == j){
        drvox[node] = (x[i] != 1);
        drvoy[node] = y[i];
        return;
    }
    int mid = i+(j-i)/2;
    build(i,mid,2*node);
    build(mid+1,j,2*node+1);
    drvox[node] = drvox[2*node]+drvox[2*node+1];
    drvoy[node] = max(drvoy[2*node],drvoy[2*node+1]);
}

void updatex(int i,int j,int pos,int val,int node){
    if(i == j){
        drvox[node] = (val != 1);
        return;
    }
    int mid = i+(j-i)/2;
    if(pos <= mid){
        updatex(i,mid,pos,val,2*node);
    }
    else{
        updatex(mid+1,j,pos,val,2*node+1);
    }
    drvox[node] = drvox[2*node]+drvox[2*node+1];
}

void updatey(int i,int j,int pos,int val,int node){
    if(i == j){
        drvoy[node] = val;
        return;
    }
    int mid = i+(j-i)/2;
    if(pos <= mid){
        updatey(i,mid,pos,val,2*node);
    }
    else{
        updatey(mid+1,j,pos,val,2*node+1);
    }
    drvoy[node] = max(drvoy[2*node],drvoy[2*node+1]);
}

int getx(int i,int j,int l,int r,int node){
    if(j < l || i > r) return 0;
    if(l <= i && r >= j) return drvox[node];
    int mid = i+(j-i)/2;
    return getx(i,mid,l,r,2*node)+getx(mid+1,j,l,r,2*node+1);
}

int gety(int i,int j,int l,int r,int node){
    if(j < l || i > r) return 0;
    if(l <= i && r >= j) return drvoy[node];
    int mid = i+(j-i)/2;
    return max(gety(i,mid,l,r,2*node),gety(mid+1,j,l,r,2*node+1));
}

ll bit[N];

void update(int pos,ll val){
    while(pos <= n){
        bit[pos] *= val;
        bit[pos] %= mod;
        pos += (pos & (-pos));
    }
}

ll daj(int pos){
    ll ret = 1;
    while(pos){
        ret *= bit[pos];
        ret %= mod;
        pos -= (pos & (-pos));
    }
    return ret;
}

ll probaj1(){
    novx = novy = {0};
    vector <pair<int,int>> v;
    int pos = n,br = 1;

    for(int pr = min(30,drvox[1]); pr >= 1; pr--){ /// nadji tacno poziciju pr-tog nejedan elementa od nazad
        int l = 1,r = n,nd = 1;
        int cuvaj = 0;
        while(l != r){
            int mid = l+(r-l)/2;
            if(cuvaj+drvox[2*nd+1] >= pr){ /// idem desno
                l = mid+1;
                nd = 2*nd+1;
            }
            else{ /// idem levo
                cuvaj += drvox[2*nd+1];
                r = mid;
                nd = 2*nd;
            }
        }

        //cout << "za " << pr << " je " << l << endl;

        if(pr == drvox[1] && l != 1){ /// tacno poslednji od nazad, onda uracunaj i keceve pre njega
            v.push_back({br,1});
            novx.push_back(1);
            /*ll sta = gety(1,n,1,l-1,1);
            novy.push_back(sta);*/
            br++;
        }

        v.push_back({br,l});
        novx.push_back(x[l]); /// y ces posle
        br++;
    }

    if(drvox[1] == 0){
        v.push_back({1,1});
        novx.push_back(1);
    }

    /*cout << "dobijam " << v.size() << endl;
    for(auto f : v){
        cout << f.first << " " << f.second << endl;
    }
    cout << novx.size() << endl;
    for(auto f : novx){
        cout << f << " ";
    }
    cout << endl;*/

    for(int i = 1; i < v.size(); i++){
        int levo = v[i-1].second,desno = v[i].second-1;
        ll sta = gety(1,n,levo,desno,1);
        novy.push_back(sta);
    }
    ll sta = gety(1,n,v.back().second,n,1);
    novy.push_back(sta);

    /*cout << novy.size() << endl;
    for(auto f : novy){
        cout << f << " ";
    }
    cout << endl;*/

    /*for(int puta = 1; puta <= 30; puta++){
        if(pos <= 0) break;

        int l = 1,r = pos,ans = 0;
        while(l <= r){
            int mid = l+(r-l)/2;
            if(getx(1,n,mid,pos,1) == 1){
                ans = mid;
                r = mid-1;
            }
            else{
                l = mid+1;
            }
        }



        if(ans == 0){
            v.push_back({br,pos});
            novx.push_back(x[pos]);
            novy.push_back(y[pos]);
            br++;
            pos--;
            continue;
        }

        ll sta = gety(1,n,ans,pos,1);


        if(ans == 1){
            v.push_back({br,ans});
            novx.push_back(x[ans]);
            novy.push_back(sta);
            pos = ans-1;
            br++;
            continue;
        }


        v.push_back({br,ans-1});
        novx.push_back(x[ans-1]);
        novy.push_back(max(y[ans-1],sta));
        pos = ans-2;
        br++;
    }*/

    /*cout << "na kraju " << endl;
    cout << v.size() << endl;
    for(auto f : v){
        cout << f.first << " " << f.second << endl;
    }
    cout << endl;
    cout << novx.size() << endl;
    for(auto f : novx){
        cout << f << " ";
    }
    cout << endl;
    cout << novy.size() << endl;
    for(auto f : novy){
        cout << f << " ";
    }
    cout << endl;*/

    sort(v.begin(),v.end(),cmp1);
    /*cout << "posle sortiranja " << v.size() << endl;
    for(auto f : v){
        cout << f.first << " " << f.second << endl;
    }*/

    /*cout << "posle sortiranja" << endl;
    cout << v.size() << endl;
    for(auto f : v){
        cout << f.first << " " << f.second << endl;
    }
    cout << endl;*/

    int poz = v[0].second;
    //cout << "poz je " << poz << endl;
    ll sol = daj(poz);
    //cout << "sol je " << sol << endl;
    ll sacim = novy[v[0].first];
    sol *= sacim;
    sol %= mod;

    return sol;
}

ll init(int n1,int *x1,int *y1){
    n = n1;
    for(int i = 1; i <= n; i++) x[i] = x1[i-1], y[i] = y1[i-1];

    /*ll pr = 1,prvi = 1;
    for(int i = 1; i <= n; i++){
        if(x[i] > 1000/pr) prvi = 0;
        else pr *= x[i];
    }
    if(n <= 10 && prvi){
        return dajdp();
    }*/

    build(1,n,1);
    for(int i = 1; i <= n; i++){
        bit[i] = 1;
    }
    for(int i = 1; i <= n; i++){
        update(i,x[i]);
    }

    return probaj1();

}

ll fp(ll x,ll y){
    if(y == 0) return 1;
    ll p = fp(x,y/2);
    p = (p*p)%mod;
    if(y&1) p = (p*x)%mod;
    return p;
}

ll updateX(int pos,int val){
    pos++;
    updatex(1,n,pos,val,1);

    ll v = fp(x[pos],mod-2);
    update(pos,v);
    v = val;
    update(pos,v);

    x[pos] = val;
    return probaj1();
}

ll updateY(int pos,int val){
    pos++;
    updatey(1,n,pos,val,1);
    y[pos] = val;
    return probaj1();
}

/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int a;
    cin >> a;
    int *prvi = (int*)malloc(sizeof(int)*a);
    int *drugi = (int*)malloc(sizeof(int)*a);
    for(int i = 1; i <= a; i++){
        int x;
        cin >> x;
        prvi[i-1] = x;
    }
    for(int i = 1; i <= a; i++){
        int x;
        cin >> x;
        drugi[i-1] = x;
    }

    cout << init(a,prvi,drugi) << endl;

    cout << updateY(1,2) << endl;
}*/

Compilation message (stderr)

horses.cpp: In function 'll dajdp()':
horses.cpp:21:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   21 |             int nagore = (j+x[i]-1)/x[i];
      |                          ~~~~~~~~~~^~~~~
horses.cpp:22:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   22 |             nagore *= x[i];
      |             ~~~~~~~^~~~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:99:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |         drvoy[node] = y[i];
      |                       ~~~^
horses.cpp: In function 'll probaj1()':
horses.cpp:224:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int i = 1; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
horses.cpp:176:9: warning: unused variable 'pos' [-Wunused-variable]
  176 |     int pos = n,br = 1;
      |         ^~~
horses.cpp: In function 'll fp(ll, ll)':
horses.cpp:350:15: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  350 | ll fp(ll x,ll y){
      |            ~~~^
horses.cpp:8:9: note: shadowed declaration is here
    8 | ll x[N],y[N];
      |         ^
horses.cpp:350:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  350 | ll fp(ll x,ll y){
      |       ~~~^
horses.cpp:8:4: note: shadowed declaration is here
    8 | ll x[N],y[N];
      |    ^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23