oj.uz

Submission #579511

# Submission time Handle Problem Language Result Execution time Memory
579511 2022-06-19T09:54:27 Z JooDdae Horses (IOI15_horses) C++17
17 / 100
 1500 ms 56256 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

const ll INF = 1e9+1;
const int mod = 1e9+7;
int n, x[500500], y[500500];
ll t1[2002002], t3[2002002];
array<int, 2> t2[2002002];
set<int> s;

ll build1(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t1[node] = x[l];
    return t1[node] = min(INF, build1(node*2, l, mid) * build1(node*2+1, mid+1, r));
}

array<int, 2> build2(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t2[node] = {y[l], l};
    return t2[node] = max(build2(node*2, l, mid), build2(node*2+1, mid+1, r));
}

ll build3(int node = 1, int l = 0, int r = n-1){
    if(l == r) return t3[node] = x[l];
    return t3[node] = build3(node*2, l, mid) * build3(node*2+1, mid+1, r) % mod;
}

void update1(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t1[node] = val;
        return;
    }
    update1(pos, val, node*2, l, mid), update1(pos, val, node*2+1, mid+1, r);
    t1[node] = min(INF, t1[node*2] * t1[node*2+1]);
}

void update2(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t2[node][0] = val;
        return;
    }
    update2(pos, val, node*2, l, mid), update2(pos, val, node*2+1, mid+1, r);
    t2[node] = max(t2[node*2], t2[node*2+1]);
}

void update3(int pos, int val, int node = 1, int l = 0, int r = n-1){
    if(pos < l || r < pos) return;
    if(l == r){
        t3[node] = val;
        return;
    }
    update3(pos, val, node*2, l, mid), update3(pos, val, node*2+1, mid+1, r);
    t3[node] = t3[node*2] * t3[node*2+1] % mod;
}

ll find1(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return 1;
    if(nl <= l && r <= nr) return t1[node];
    return min(INF, find1(nl, nr, node*2, l, mid) * find1(nl, nr, node*2+1, mid+1, r));
}

array<int, 2> find2(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return {0, 0};
    if(nl <= l && r <= nr) return t2[node];
    return max(find2(nl, nr, node*2, l, mid), find2(nl, nr, node*2+1, mid+1, r));
}

ll find3(int nl, int nr, int node = 1, int l = 0, int r = n-1){
    if(nr < l || r < nl) return 1;
    if(nl <= l && r <= nr) return t3[node];
    return find3(nl, nr, node*2, l, mid) * find3(nl, nr, node*2+1, mid+1, r) % mod;
}

int find_max(int l, int r){
    if(l == r) return r;
    ll k = x[r] * y[r];
    auto mx = find2(l, r-1);
    return k > mx[0] ? r : mx[1];
}

int solve(){
    auto it = s.rbegin();
    int mx = find_max(*prev(it)+1, *it);

    for(int k=n-1;k<n;k++){
        assert(y[mx] >= find1(mx+1, k) * y[k]);
    }

    for(int k=mx-1;k>=0;k--){
        if(y[k] > find1(k+1, mx) * y[mx]) mx = k;
    }

    return find3(0, mx) * y[mx] % mod;
}

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

    s.insert(-1);
    for(int i=0;i<N;i++) if(x[i] > 1) s.insert(i);
    s.insert(N-1);

    build1(), build2(), build3();

    return solve();
}

int updateX(int pos, int val) { 
    if(pos < n-1 && x[pos] > 1) s.erase(pos);
    x[pos] = val, update1(pos, val), update3(pos, val);
    if(x[pos] > 1) s.insert(pos);
    return solve();
}

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

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:97:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |     return find3(0, mx) * y[mx] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 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 Runtime error 1 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 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 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Runtime error 2 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Runtime error 2 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -