oj.uz

Submission #795672

# Submission time Handle Problem Language Result Execution time Memory
795672 2023-07-27T12:40:46 Z jasmin Horses (IOI15_horses) C++17
0 / 100
 127 ms 27744 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

const long long MOD=1e9+7;
int n=0;
vector<int> x;
vector<int> y;

struct segtree{
    vector<int> tree;
    vector<int> lazy;

    void init(){
        tree.assign(n*4, 0);
        lazy.assign(n*4, 1);
    }

    int MUL(int a, int b){
        return (a*b)%MOD;
    }

    int update_node(int l, int r, int v, int val){
        lazy[v] = MUL(lazy[v], val);
        return tree[v] = MUL(lazy[v], val);
    }

    void propagate(int l, int r, int v){
        if(lazy[v]==1) return;

        int m=l+(r-l)/2;
        update_node(l, m, v*2+1, lazy[v]);
        update_node(m, r, v*2+2, lazy[v]);
        lazy[v]=1;
    }

    int update(int l, int r, int v, int ql, int qr, int val){
        if(qr<=l || r<=qr) return tree[v];
        if(ql<=l && r<=qr){

            return update_node(l, r, v, val);
        }
        propagate(l, r, v);
        int m=l+(r-l)/2;
        return tree[v] = MUL(update(l, m, v*2+1, ql, qr, val), update(m, r, v*2+2, ql, qr, val));
    }

    int query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return 1;
        if(ql<=l && r<=qr){
            return tree[v];
        }
        propagate(l, r, v);
        int m=l+(r-l)/2;
        return MUL(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }

};
segtree seg;

bool bigger(pair<int, long long> a, pair<int, long long> b){
    return a.first*b.second > a.second*b.first;
}

int solveSlow(){

    long long p=1; bool mod=false;
    pair<int, long long> maxi={1, 1}; 
    int ind=n-1;

    for(int i=n-1; i>=0; i--){

        if(!mod){
            
            if(bigger({y[i], p}, maxi)){
                maxi={y[i], p};
                ind=i;
            }
            
        }

        p*=(long long)x[i];
        if(p > MOD){
            p%=MOD;
            mod=true;
        }

    }

    long long ans=1;
    for(int i=0; i<=ind; i++){
        ans *= (long long)x[i];
        ans%=MOD;
    }

    ans *= (long long)y[ind];
    ans%=MOD;

    return ans;
}

int solve3(){

    long long p=1; bool mod=false;
    pair<int, long long> maxi={1, 1}; 
    int ind=n-1;

    for(int i=n-1; i>=max(0, n-32); i--){

        if(!mod){
            
            if(bigger({y[i], p}, maxi)){
                maxi={y[i], p};
                ind=i;
            }
            
        }

        p*=(long long)x[i];
        if(p > MOD){
            p%=MOD;
            mod=true;
        }

    }

    long long ans=seg.query(0, n, 0, 0, ind+1);

    ans *= (long long)y[ind];
    ans%=MOD;

    return ans;

}

int solve(){

    bool one=false;
    for(int i=n-1; i>=max(0, n-32); i--){
        if(x[i]==1) one=true;
    }

    if(one){
        return solveSlow();
    }
    return solve3();
}

int init(int N, int X[], int Y[]) {
    n=N;
    x.assign(n, 0);
    y.assign(n, 0);
    for(int i=0; i<N; i++){
        x[i]=X[i];
        y[i]=Y[i];
    }

    int px=x[0];
    seg.init();
    seg.update(0, n, 0, 0, 1, px);
    for(int i=1; i<n; i++){
        px*=x[i];
        px%=MOD;

        seg.update(0, n, 0, i, i+1, px);
    }

	return solve();
}

int fastpow(int a, int b){
    if(b==0) return 1;

    int s=fastpow(a, b/2);
    s=s*s;
    s%=MOD;

    if(b%2==0){
        s*=a;
        s%=MOD;
    }
    return s;
}

int inverse(int a){
    return fastpow(a, MOD-2);
}

int updateX(int pos, int val) {	

    int change = val * inverse(x[pos]); //val/x[pos]
    change%=MOD;
	
    x[pos]=val;
    seg.update(0, n, 0, pos, n, change);
    return solve();
}

int updateY(int pos, int val) {
	
    y[pos]=val;
    return solve();
}

Compilation message

horses.cpp: In member function 'int segtree::update_node(int, int, int, int)':
horses.cpp:23:25: warning: unused parameter 'l' [-Wunused-parameter]
   23 |     int update_node(int l, int r, int v, int val){
      |                     ~~~~^
horses.cpp:23:32: warning: unused parameter 'r' [-Wunused-parameter]
   23 |     int update_node(int l, int r, int v, int val){
      |                            ~~~~^
horses.cpp: In function 'int solveSlow()':
horses.cpp:99:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |     return ans;
      |            ^~~
horses.cpp: In function 'int solve3()':
horses.cpp:132:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |     return ans;
      |            ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 27744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -