oj.uz

Submission #47365

# Submission time Handle Problem Language Result Execution time Memory
47365 2018-05-01T16:36:05 Z aquablitz11 Horses (IOI15_horses) C++14
100 / 100
 459 ms 148432 KB 
// headers
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// types
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using dbl = double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using piipi = pair<pii, int>;
using pipii = pair<int, pii>;
using plpii = pair<ll, pii>;
using ppii = pair<pii, pii>;
// loops
#define forx(i, x, y) for (int i = (x); i <= (y); ++i)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define for1(i, n) for (int i = 1; i <= (n); ++i)
#define rofx(i, x, y) for (int i = x; i >= y; --i)
#define rofn(i, n) for (int i = n-1; i >= 0; --i)
#define rof1(i, n) for (int i = n; i >= 1; --i)
#define fora(x, v) for (auto x : v)
// define shortcuts
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
// functions
template<class T> inline bool hasbit(T x, int i) { return x&(1<<i); }
template<class T> inline T togbit(T x, int i) { return x|(1<<i); }
template<class T> inline T setbit(T x, int i) { return x|(1<<i); }
template<class T> inline T rembit(T x, int i) { return x&~(1<<i); }
template<class T> inline bool setmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool setmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> int compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v))-v.begin()); return v.size(); }
// read functions
int read_int() { int x; scanf("%d", &x); return x; }
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
void _R(int &x) { x = read_int(); }
void _R(ll &x) { x = read_ll(); }
void _R(dbl &x) { x = read_dbl(); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
// print functions
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%" PRId64, x); }
void _W(const ull &x) { printf("%" PRIu64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
// pseudo-random number generator
template<class T, T x1, T x2, T x3, int y1, int y2, int y3>
struct PRNG {
    using S = typename make_signed<T>::type;
    T s;
    PRNG(T _s = 0) : s(_s) {}
    T next() {
        T z = (s += x1);
        z = (z ^ (z >> y1)) * x2;
        z = (z ^ (z >> y2)) * x3;
        return z ^ (z >> y3);
    }
    T next(T n) { return next() % n; }
    S next(S l, S r) { return l + next(r - l + 1); }
    T operator()() { return next(); }
    T operator()(T n) { return next(n); }
    S operator()(S l, S r) { return next(l, r); }
    static T gen(T s) { return PRNG(s)(); }
    template<class U>
    void shuffle(U first, U last) {
        size_t n = last - first;
        for (size_t i = 0; i < n; i++) swap(first[i], first[next(i + 1)]);
    }
};
PRNG<uint32_t, 0x9E3779B1, 0x85EBCA6B, 0xC2B2AE35, 16, 13, 16> r32;
PRNG<uint64_t, 0x9E3779B97F4A7C15, 0xBF58476D1CE4E5B9, 0x94D049BB133111EB, 30, 27, 31> r64;

/************************************************************
                CODE STARTS BELOW THIS POINT
************************************************************/

#include "horses.h"

const int MOD = 1e9+7;
const int N = 500010;

int mul(int a, int b) { return (a*1ll*b)%MOD; }

int n, seg[N<<1], seg2[N<<1];
int X[N], Y[N];

int query(int l, int r)
{
    int ans = 1;
    for (l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
        if (l&1) ans = mul(ans, seg[l++]);
        if (r&1) ans = mul(ans, seg[--r]);
    }
    return ans;
}

int query2(int l, int r)
{
    int ans = 0;
    for (l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
        if (l&1) setmax(ans, seg2[l++]);
        if (r&1) setmax(ans, seg2[--r]);
    }
    return ans;
}

void update(int p, int x)
{
    for (seg[p += n] = x; p >>= 1; )
        seg[p] = mul(seg[p<<1], seg[p<<1|1]);
}

void update2(int p, int x)
{
    for (seg2[p += n] = x; p >>= 1; )
        seg2[p] = max(seg2[p<<1], seg2[p<<1|1]);
}

set<int, greater<int>> xpos;

int findans() {
    ll val = 1;
    auto j = xpos.begin();
    for (auto it = xpos.begin(); it != xpos.end(); ++it) {
        val *= X[*it];
        j = it;
        if (val > 1e9) break;
    }
    val = 1;
    ll best = 0;
    for (auto it = j; ; --it) {
        val *= it == j ? 1 : X[*it];
        setmax(best, val * query2(*it, n-1));
        if (it == xpos.begin()) break;
    }
    best %= MOD;
    return mul(query(0, *j), best);
}

int init(int N, int X[], int Y[]) {
    n = N;
    forn(i, n) {
        ::X[i] = X[i], seg[n+i] = X[i], ::Y[i] = Y[i], seg2[n+i] = Y[i];
        if (X[i] > 1) xpos.insert(i);
    }
    ::X[n] = 1;
    xpos.insert(0);
    rof1(i, n-1) seg[i] = mul(seg[i<<1], seg[i<<1|1]), seg2[i] = max(seg2[i<<1], seg2[i<<1|1]);
    return findans();
}

int updateX(int pos, int val) {	
    if (val > 1)
        xpos.insert(pos);
    if (val == 1 && pos != 0)
        xpos.erase(pos);
    X[pos] = val;
    update(pos, val);
    return findans();
}

int updateY(int pos, int val) {
    Y[pos] = val;
    update2(pos, val);
    return findans();
}

Compilation message

horses.cpp: In function 'll read_ll()':
horses.cpp:49:42: warning: format '%ld' expects argument of type 'long int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
 ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
                                        ~~^
horses.cpp: In function 'ull read_ull()':
horses.cpp:50:45: warning: format '%lu' expects argument of type 'long unsigned int*', but argument 2 has type 'ull* {aka long long unsigned int*}' [-Wformat=]
 ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
                                           ~~^
horses.cpp: In function 'void _W(const ll&)':
horses.cpp:60:44: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
 void _W(const ll &x) { printf("%" PRId64, x); }
                                           ~^
horses.cpp: In function 'void _W(const ull&)':
horses.cpp:61:45: warning: format '%lu' expects argument of type 'long unsigned int', but argument 2 has type 'ull {aka long long unsigned int}' [-Wformat=]
 void _W(const ull &x) { printf("%" PRIu64, x); }
                                            ~^
horses.cpp: In function 'int mul(int, int)':
horses.cpp:104:41: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 int mul(int a, int b) { return (a*1ll*b)%MOD; }
                                ~~~~~~~~~^~~~
horses.cpp: In function 'int findans()':
horses.cpp:149:19: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
         if (val > 1e9) break;
                   ^~~
horses.cpp:159:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return mul(query(0, *j), best);
                                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:162:33: warning: declaration of 'second' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:36:11: note: shadowed declaration is here
 #define Y second
           ^
horses.cpp:107:11: note: in expansion of macro 'Y'
 int X[N], Y[N];
           ^
horses.cpp:162:33: warning: declaration of 'first' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:35:11: note: shadowed declaration is here
 #define X first
           ^
horses.cpp:107:5: note: in expansion of macro 'X'
 int X[N], Y[N];
     ^
horses.cpp:162:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:102:11: note: shadowed declaration is here
 const int N = 500010;
           ^
horses.cpp: In function 'int read_int()':
horses.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 int read_int() { int x; scanf("%d", &x); return x; }
                         ~~~~~^~~~~~~~~~
horses.cpp: In function 'll read_ll()':
horses.cpp:49:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
                      ~~~~~^~~~~~~~~~~~~~~~
horses.cpp: In function 'ull read_ull()':
horses.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
                         ~~~~~^~~~~~~~~~~~~~~~
horses.cpp: In function 'dbl read_dbl()':
horses.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
                         ~~~~~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 636 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 640 KB Output is correct
18 Correct 2 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 2 ms 696 KB Output is correct
25 Correct 3 ms 696 KB Output is correct
26 Correct 3 ms 696 KB Output is correct
27 Correct 3 ms 696 KB Output is correct
28 Correct 3 ms 696 KB Output is correct
29 Correct 2 ms 696 KB Output is correct
30 Correct 2 ms 696 KB Output is correct
31 Correct 2 ms 708 KB Output is correct
32 Correct 3 ms 708 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 40796 KB Output is correct
2 Correct 398 ms 40872 KB Output is correct
3 Correct 366 ms 40872 KB Output is correct
4 Correct 435 ms 40872 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 40872 KB Output is correct
2 Correct 2 ms 40872 KB Output is correct
3 Correct 2 ms 40872 KB Output is correct
4 Correct 2 ms 40872 KB Output is correct
5 Correct 2 ms 40872 KB Output is correct
6 Correct 2 ms 40872 KB Output is correct
7 Correct 2 ms 40872 KB Output is correct
8 Correct 2 ms 40872 KB Output is correct
9 Correct 2 ms 40872 KB Output is correct
10 Correct 2 ms 40872 KB Output is correct
11 Correct 2 ms 40872 KB Output is correct
12 Correct 2 ms 40872 KB Output is correct
13 Correct 2 ms 40872 KB Output is correct
14 Correct 2 ms 40872 KB Output is correct
15 Correct 2 ms 40872 KB Output is correct
16 Correct 2 ms 40872 KB Output is correct
17 Correct 2 ms 40872 KB Output is correct
18 Correct 2 ms 40872 KB Output is correct
19 Correct 2 ms 40872 KB Output is correct
20 Correct 2 ms 40872 KB Output is correct
21 Correct 2 ms 40872 KB Output is correct
22 Correct 2 ms 40872 KB Output is correct
23 Correct 2 ms 40872 KB Output is correct
24 Correct 2 ms 40872 KB Output is correct
25 Correct 3 ms 40872 KB Output is correct
26 Correct 2 ms 40872 KB Output is correct
27 Correct 3 ms 40872 KB Output is correct
28 Correct 2 ms 40872 KB Output is correct
29 Correct 2 ms 40872 KB Output is correct
30 Correct 3 ms 40872 KB Output is correct
31 Correct 3 ms 40872 KB Output is correct
32 Correct 3 ms 40872 KB Output is correct
33 Correct 36 ms 40872 KB Output is correct
34 Correct 37 ms 40872 KB Output is correct
35 Correct 273 ms 40872 KB Output is correct
36 Correct 288 ms 40872 KB Output is correct
37 Correct 40 ms 40872 KB Output is correct
38 Correct 125 ms 40872 KB Output is correct
39 Correct 27 ms 40872 KB Output is correct
40 Correct 282 ms 45756 KB Output is correct
41 Correct 29 ms 45756 KB Output is correct
42 Correct 32 ms 45756 KB Output is correct
43 Correct 268 ms 56248 KB Output is correct
44 Correct 285 ms 62744 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 62744 KB Output is correct
2 Correct 2 ms 62744 KB Output is correct
3 Correct 2 ms 62744 KB Output is correct
4 Correct 2 ms 62744 KB Output is correct
5 Correct 2 ms 62744 KB Output is correct
6 Correct 2 ms 62744 KB Output is correct
7 Correct 2 ms 62744 KB Output is correct
8 Correct 2 ms 62744 KB Output is correct
9 Correct 2 ms 62744 KB Output is correct
10 Correct 2 ms 62744 KB Output is correct
11 Correct 2 ms 62744 KB Output is correct
12 Correct 2 ms 62744 KB Output is correct
13 Correct 2 ms 62744 KB Output is correct
14 Correct 2 ms 62744 KB Output is correct
15 Correct 2 ms 62744 KB Output is correct
16 Correct 2 ms 62744 KB Output is correct
17 Correct 2 ms 62744 KB Output is correct
18 Correct 2 ms 62744 KB Output is correct
19 Correct 2 ms 62744 KB Output is correct
20 Correct 2 ms 62744 KB Output is correct
21 Correct 2 ms 62744 KB Output is correct
22 Correct 2 ms 62744 KB Output is correct
23 Correct 2 ms 62744 KB Output is correct
24 Correct 2 ms 62744 KB Output is correct
25 Correct 3 ms 62744 KB Output is correct
26 Correct 2 ms 62744 KB Output is correct
27 Correct 3 ms 62744 KB Output is correct
28 Correct 3 ms 62744 KB Output is correct
29 Correct 2 ms 62744 KB Output is correct
30 Correct 2 ms 62744 KB Output is correct
31 Correct 3 ms 62744 KB Output is correct
32 Correct 3 ms 62744 KB Output is correct
33 Correct 346 ms 63672 KB Output is correct
34 Correct 405 ms 63676 KB Output is correct
35 Correct 375 ms 63676 KB Output is correct
36 Correct 459 ms 63676 KB Output is correct
37 Correct 40 ms 63676 KB Output is correct
38 Correct 36 ms 63676 KB Output is correct
39 Correct 269 ms 63676 KB Output is correct
40 Correct 289 ms 63676 KB Output is correct
41 Correct 39 ms 63676 KB Output is correct
42 Correct 132 ms 63676 KB Output is correct
43 Correct 26 ms 63676 KB Output is correct
44 Correct 282 ms 68792 KB Output is correct
45 Correct 28 ms 68792 KB Output is correct
46 Correct 33 ms 68792 KB Output is correct
47 Correct 255 ms 79260 KB Output is correct
48 Correct 281 ms 85604 KB Output is correct
49 Correct 110 ms 85604 KB Output is correct
50 Correct 105 ms 85604 KB Output is correct
51 Correct 363 ms 108412 KB Output is correct
52 Correct 331 ms 119824 KB Output is correct
53 Correct 185 ms 119824 KB Output is correct
54 Correct 221 ms 119824 KB Output is correct
55 Correct 199 ms 119824 KB Output is correct
56 Correct 354 ms 136984 KB Output is correct
57 Correct 88 ms 136984 KB Output is correct
58 Correct 122 ms 136984 KB Output is correct
59 Correct 300 ms 148432 KB Output is correct