Submission #839296

#	Time	Username	Problem	Language	Result	Execution time	Memory
839296		Cookie	Horses (IOI15_horses)	C++14	100 / 100	591 ms	65456 KiB

horses

#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;){
            if(mul > inf)break;
            if(x[j] >= 2){
                if(y[j] > mul){
                    mul = y[j]; idbest = j;
                }
                mul = mul * x[j];
                j--;
            }else{
                auto it = special.lower_bound(j);
                int id = -1;
                if(it != special.begin()){
                    --it;
                    id = *it;
                }
                auto [mxy, idy] = get(1, 0, n - 1, id + 1, j);
                if(mxy > mul){
                    mul = mxy; idbest = idy;
                }
                
                j = id;
            }
            
            
        }
        
    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];
        if(x[i] > 1){
            special.insert(i);
        }
        
        updprod(1, 0, n - 1, i, x[i]);
    }
    for(int i = 0; i < n; i++){
        y[i] = Y[i];
        upd(1, 0, n - 1, i, y[i]);
    }
    
    return(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 (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:87:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |                 auto [mxy, idy] = get(1, 0, n - 1, id + 1, j);
      |                      ^
horses.cpp:98:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |     return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
      |                                     ^~~~~~
horses.cpp:98:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |     return((getprod(1, 0, n - 1, 0, idbest) * y[idbest]) % mod);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:112:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |         upd(1, 0, n - 1, i, y[i]);
      |                             ~~~^

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