oj.uz

Submission #839290

# Submission time Handle Problem Language Result Execution time Memory
839290 2023-08-29T15:22:47 Z Cookie Horses (IOI15_horses) C++14
0 / 100
 1500 ms 108900 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include "horses.h"
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxr = 25e3, sq = 500, mxv = 200, mxvv = 130, pr = 31;
const ll inf = 1e9;
int n, m;
pii st[4 * mxn + 1];
ll prod[4 * mxn + 1], x[mxn + 1], y[mxn + 1];
set<int>special;
void updprod(int nd, int l, int r, int id, ll v){
    if(id < l || id > r)return;
    if(l == r){
        prod[nd] = v;
        return;
    }
    int mid = (l + r) >> 1;
    updprod(nd << 1, l, mid, id, v); updprod(nd << 1 | 1, mid + 1, r, id, v);
    prod[nd] = (prod[nd << 1] * prod[nd << 1 | 1]) % mod;
}
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        st[nd] = make_pair(v, id);
        return;
    }
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
ll getprod(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(1);
    if(ql <= l && qr >= r)return(prod[nd]);
    int mid = (l + r) >> 1;
    return((getprod(nd << 1, l, mid, ql, qr) * getprod(nd << 1 | 1, mid + 1, r, ql, qr)) % mod);
}
pii get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(make_pair(-1, -1));
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
void updx(int pos, int val){
    if(x[pos] == 1)special.erase(pos);
    x[pos] = val;
    if(x[pos] == 1)special.insert(pos);
    updprod(1, 0, n - 1, pos, val);
}
void updy(int pos, int val){
    y[pos] = val;
    upd(1, 0, n - 1, pos, val);
}
int solve(){
    ll mul = 0, idbest = n - 1;
        for(int j = n - 1; j >= 0; j--){
            if(mul > inf)break;
            if(y[j] > mul){
                mul = y[j]; idbest = j;
            }
            mul = mul * x[j];
            
        }
        
    return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
}
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; i++)x[i] = X[i];
    for(int i = 0; i < n; i++)y[i] = Y[i];
	for(int i = 0; i < n; i++){
        cin >> x[i]; 
        if(x[i] > 1){
            special.insert(i);
        }
        
        updprod(1, 0, n - 1, i, x[i]);
    }
    for(int i = 0; i < n; i++){
        cin >> y[i]; 
        assert(y[i] <= inf);
        upd(1, 0, n - 1, i, y[i]);
    }
    solve();
}

int updateX(int pos, int val) {	
    updx(pos, val);
	return(solve());
}

int updateY(int pos, int val) {
    updy(pos, val);
	return(solve());
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:81:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |     return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
      |                                     ^~~~~~
horses.cpp:81:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |     return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |         upd(1, 0, n - 1, i, y[i]);
      |                             ~~~^
horses.cpp:100:10: warning: control reaches end of non-void function [-Wreturn-type]
  100 |     solve();
      |     ~~~~~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1547 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1547 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 400 ms 108900 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1538 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -