oj.uz

Submission #839294

# Submission time Handle Problem Language Result Execution time Memory
839294 2023-08-29T15:25:44 Z Cookie Horses (IOI15_horses) C++14
17 / 100
 1500 ms 51944 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;){
            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];
    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]);
    }
    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

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:115:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |         upd(1, 0, n - 1, i, y[i]);
      |                             ~~~^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 312 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Execution timed out 1541 ms 340 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Execution timed out 1579 ms 340 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 0 ms 224 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Execution timed out 1578 ms 340 KB Time limit exceeded
24 Halted 0 ms 0 KB -