oj.uz

Submission #586795

# Submission time Handle Problem Language Result Execution time Memory
586795 2022-06-30T17:13:26 Z InternetPerson10 Horses (IOI15_horses) C++17
17 / 100
 507 ms 81744 KB 
#include "horses.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MOD = 1e9 + 7;

vector<int> x, y;
set<int> nonOnes;

ll modpow(ll n, ll e = MOD - 2) {
    if(e == 0) return 1;
    ll g = modpow(n, e/2);
    g *= g;
    g %= MOD;
    if(e%2) {
        g *= n;
        g %= MOD;
    }
    return g;
}

struct SegTree {
    int lx, rx;
    int val = 0;
    SegTree *ls, *rs;
    SegTree(int l, int r) : lx(l), rx(r) {
        if(rx - lx != 1) {
            int mid = (lx + rx) / 2;
            ls = new SegTree(l, mid);
            rs = new SegTree(mid, r);
            val = max(ls->val, rs->val);
        }
        else {
            if(lx < (int)y.size()) val = y[lx];
        }
    }
    int getMax(int l, int r) {
        if(r <= lx || rx <= l) return 0;
        if(l <= lx && rx <= r) return val;
        return max(ls->getMax(l, r), rs->getMax(l, r));
    }
    int changeVal(int g) {
        if(g+1 <= lx || rx <= g) return val;
        if(g <= lx && rx <= g+1) {
            val = y[g];
            return val;
        }
        return val = max(ls->changeVal(g), rs->changeVal(g));
    }
};

ll prod = 1;
SegTree *st;

ll recalc() {
    ll currProd = 1;
    auto it = nonOnes.end();
    int rightBorder = x.size();
    do {
        it--;
        int idx = *it;
        int val = x[idx];
        currProd *= val;
        if((currProd > 1000000000) || (it == nonOnes.begin())) {
            if(currProd > 1000000000) {
                currProd /= val;
                it++;
            }
            ll best = -1, base = prod * modpow(currProd);
            auto it2 = nonOnes.end();
            do {
                it2--;
                best = max(best, currProd * st->getMax((*it2), rightBorder));
                rightBorder = (*it2);
                currProd /= x[(*it2)];
            } while(it2 != it);
            assert(currProd == 1);
            return ((best % MOD) * (base % MOD)) % MOD;
        }
    } while(it != nonOnes.begin());
    assert(false);
}

int init(int n, int X[], int Y[]) {
    x.resize(n);
    y.resize(n);
    for(int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
    }
    // Process X
    nonOnes.insert(0);
    for(int i = 0; i < n; i++) {
        if(x[i] != 1) nonOnes.insert(i);
        prod *= x[i];
        prod %= MOD;
    }
    // Process Y
    int g = 1;
    while(g < n) g *= 2;
    st = new SegTree(0, g);
	return recalc();
}

int updateX(int pos, int val) {
    prod *= modpow(x[pos]);
    prod %= MOD;
    x[pos] = val;
    prod *= x[pos];
    prod %= MOD;
    if(pos) {
        nonOnes.erase(pos);
        if(val != 1) nonOnes.insert(pos);
    }
    return recalc();
}

int updateY(int pos, int val) {	
    y[pos] = val;
    st->changeVal(pos);
    return recalc();
}

Compilation message

horses.cpp: In function 'll recalc()':
horses.cpp:60:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |     int rightBorder = x.size();
      |                       ~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  103 |  return recalc();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:116:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |     return recalc();
      |            ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |     return recalc();
      |            ~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 81744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 212 KB Output is correct
12 Correct 0 ms 272 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 224 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 1 ms 304 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -