oj.uz

Submission #597134

# Submission time Handle Problem Language Result Execution time Memory
597134 2022-07-15T14:35:25 Z PiejanVDC Horses (IOI15_horses) C++17
17 / 100
 1500 ms 74888 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long>x,y;

long long mod = (long long)1000000007;

int last;
int ans;

int l,r;

vector<long long>mul(8*500000), correct_mul(8*500000);

void build(int i, int j, int p) {
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    build(i, mid, 2*p);
    build(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

long long get_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return mul[p];
    int mid = (i+j)/2;
    return min(get_mul(i, mid, 2*p) * get_mul(mid+1, j, 2*p+1), (long long)1e9+5);
}

long long get_correct_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return correct_mul[p];
    int mid = (i+j)/2;
    return (get_correct_mul(i, mid, 2*p) * get_correct_mul(mid+1, j, 2*p+1))%mod;
}

void update(int i, int j, int p) {
    if(i > l || j < l)
        return;
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

int updX(int p) {
    int n = x.size();
    if(p <= last)
        return ans;
    l = last+1, r = p;
    if(get_mul(0, n-1, 1) * y[p] > ans) {
        last = p;
        l = 0, r = p;
        return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
    }
}

int calc();

int updY(int p) {
    int n = x.size();
    if(p == last)
        return calc();
    if(p < last) {
        l = p+1, r = last;
        if(get_mul(0, n-1, 1) * y[last] > y[p])
            return ans;
        else {
            last = p;
            l = 0, r = p;
            return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
        }
    } else {
        l = last+1, r = p;
        if(get_mul(0, n-1, 1) * y[p] > y[last]) {
            last = p;
            l = 0, r = p;
            return ans = int((get_correct_mul(0, n-1, 1) * y[last])%mod);
        } else {
            return ans;
        }
    }
}

int calc() {
    int n = (int)x.size();

    build(0, n-1, 1);

    last = -1;

    bool ok = 1;
    while(ok) {
        ok = 0;
        long long c = 1;
        for(int i = last+1 ; i < n ; i++) {
            c *= x[i];
            c = min(c, (long long)1e9+5);
            if(c * y[i] > (last == -1 ? 0 : y[last])) {
                last = i;
                ok = 1;
                break;
            }
        }
    }

    long long C = 1;
    for(int i = 0 ; i <= last ; i++)
        C *= x[i], C %= mod;
    return ans = int((C * y[last])%mod);
}

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

int updateX(int p, int val) {
    int n = (int)x.size();
    x[p] = val;
    update(0, n-1, 1);
    return updX(p);
}

int updateY(int p, int val) {
    int n = (int)x.size();
    y[p] = val;
    return updY(p);
}

Compilation message

horses.cpp: In function 'int updX(int)':
horses.cpp:65:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   65 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp: In function 'int updY(int)':
horses.cpp:79:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:145:9: warning: unused variable 'n' [-Wunused-variable]
  145 |     int n = (int)x.size();
      |         ^
horses.cpp: In function 'int updX(int)':
horses.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62876 KB Output is correct
2 Correct 26 ms 62892 KB Output is correct
3 Correct 24 ms 62888 KB Output is correct
4 Correct 25 ms 62908 KB Output is correct
5 Correct 24 ms 62856 KB Output is correct
6 Correct 26 ms 62876 KB Output is correct
7 Correct 23 ms 62932 KB Output is correct
8 Correct 22 ms 62916 KB Output is correct
9 Correct 24 ms 62816 KB Output is correct
10 Correct 23 ms 62876 KB Output is correct
11 Correct 28 ms 62932 KB Output is correct
12 Correct 22 ms 62900 KB Output is correct
13 Correct 30 ms 62884 KB Output is correct
14 Correct 24 ms 62804 KB Output is correct
15 Correct 23 ms 62796 KB Output is correct
16 Correct 27 ms 62844 KB Output is correct
17 Correct 22 ms 62836 KB Output is correct
18 Correct 29 ms 62912 KB Output is correct
19 Correct 24 ms 62840 KB Output is correct
20 Correct 26 ms 62932 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62916 KB Output is correct
2 Correct 27 ms 62872 KB Output is correct
3 Correct 27 ms 62932 KB Output is correct
4 Correct 23 ms 62912 KB Output is correct
5 Correct 32 ms 62864 KB Output is correct
6 Correct 29 ms 62860 KB Output is correct
7 Correct 27 ms 62900 KB Output is correct
8 Correct 26 ms 62904 KB Output is correct
9 Correct 23 ms 62880 KB Output is correct
10 Correct 26 ms 62900 KB Output is correct
11 Correct 24 ms 62932 KB Output is correct
12 Correct 23 ms 62856 KB Output is correct
13 Correct 24 ms 62900 KB Output is correct
14 Correct 26 ms 62836 KB Output is correct
15 Correct 30 ms 62808 KB Output is correct
16 Correct 27 ms 62908 KB Output is correct
17 Correct 23 ms 62804 KB Output is correct
18 Correct 24 ms 62896 KB Output is correct
19 Correct 23 ms 62932 KB Output is correct
20 Correct 23 ms 62812 KB Output is correct
21 Incorrect 24 ms 62936 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62932 KB Output is correct
2 Correct 24 ms 62812 KB Output is correct
3 Correct 24 ms 62900 KB Output is correct
4 Correct 24 ms 62852 KB Output is correct
5 Correct 25 ms 62932 KB Output is correct
6 Correct 25 ms 62920 KB Output is correct
7 Correct 28 ms 62928 KB Output is correct
8 Correct 24 ms 62804 KB Output is correct
9 Correct 24 ms 62804 KB Output is correct
10 Correct 24 ms 62844 KB Output is correct
11 Correct 24 ms 62912 KB Output is correct
12 Correct 24 ms 62932 KB Output is correct
13 Correct 23 ms 62856 KB Output is correct
14 Correct 24 ms 62924 KB Output is correct
15 Correct 23 ms 62932 KB Output is correct
16 Correct 24 ms 62896 KB Output is correct
17 Correct 23 ms 62844 KB Output is correct
18 Correct 24 ms 62872 KB Output is correct
19 Correct 25 ms 62900 KB Output is correct
20 Correct 23 ms 62816 KB Output is correct
21 Incorrect 26 ms 62824 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62936 KB Output is correct
2 Correct 23 ms 62876 KB Output is correct
3 Correct 23 ms 62928 KB Output is correct
4 Correct 25 ms 62896 KB Output is correct
5 Correct 23 ms 62828 KB Output is correct
6 Correct 23 ms 62864 KB Output is correct
7 Correct 23 ms 62932 KB Output is correct
8 Correct 25 ms 62936 KB Output is correct
9 Correct 23 ms 62868 KB Output is correct
10 Correct 24 ms 62884 KB Output is correct
11 Correct 24 ms 62844 KB Output is correct
12 Correct 28 ms 62904 KB Output is correct
13 Correct 24 ms 62868 KB Output is correct
14 Correct 24 ms 62796 KB Output is correct
15 Correct 25 ms 62860 KB Output is correct
16 Correct 23 ms 62948 KB Output is correct
17 Correct 26 ms 62816 KB Output is correct
18 Correct 24 ms 62860 KB Output is correct
19 Correct 22 ms 62908 KB Output is correct
20 Correct 23 ms 62908 KB Output is correct
21 Incorrect 22 ms 62864 KB Output isn't correct
22 Halted 0 ms 0 KB -