oj.uz

Submission #47362

# Submission time Handle Problem Language Result Execution time Memory
47362 2018-05-01T16:11:04 Z aquablitz11 Horses (IOI15_horses) C++14
17 / 100
 62 ms 17844 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];
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;
}

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

int findans() {
    ll val = 1;
    int j;
    rofn(i, n) {
        val *= X[i];
        if (val > 1e9)
            break;
        j = i;
    }
    val = 1;
    ll best = 0;
    forx(i, j, n-1) {
        val *= X[i];
        setmax(best, val * Y[i]);
    }
    best %= MOD;
    return mul(query(0, j-1), 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];
    rof1(i, n-1) seg[i] = mul(seg[i<<1], seg[i<<1|1]);
    return findans();
}

int updateX(int pos, int val) {	
    X[pos] = val;
    update(pos, val);
    return findans();
}

int updateY(int pos, int val) {
    Y[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:130:19: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
         if (val > 1e9)
                   ^~~
horses.cpp:141:35: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return mul(query(0, j-1), best);
                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:144: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:144: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:144: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; }
                         ~~~~~^~~~~~~~~~~
horses.cpp: In function 'int findans()':
horses.cpp:127:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int j;
         ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 684 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 728 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 884 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 2 ms 908 KB Output is correct
13 Correct 2 ms 912 KB Output is correct
14 Correct 2 ms 916 KB Output is correct
15 Correct 2 ms 920 KB Output is correct
16 Correct 2 ms 928 KB Output is correct
17 Correct 2 ms 928 KB Output is correct
18 Correct 2 ms 932 KB Output is correct
19 Correct 2 ms 936 KB Output is correct
20 Correct 2 ms 940 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1072 KB Output is correct
2 Correct 2 ms 1080 KB Output is correct
3 Correct 2 ms 1084 KB Output is correct
4 Correct 2 ms 1084 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 2 ms 1124 KB Output is correct
13 Correct 2 ms 1128 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1136 KB Output is correct
16 Correct 2 ms 1140 KB Output is correct
17 Correct 2 ms 1144 KB Output is correct
18 Correct 2 ms 1148 KB Output is correct
19 Correct 2 ms 1152 KB Output is correct
20 Correct 2 ms 1152 KB Output is correct
21 Correct 2 ms 1160 KB Output is correct
22 Correct 2 ms 1164 KB Output is correct
23 Incorrect 3 ms 1172 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17844 KB Output is correct
2 Correct 2 ms 17844 KB Output is correct
3 Correct 2 ms 17844 KB Output is correct
4 Correct 2 ms 17844 KB Output is correct
5 Correct 2 ms 17844 KB Output is correct
6 Correct 2 ms 17844 KB Output is correct
7 Correct 2 ms 17844 KB Output is correct
8 Correct 2 ms 17844 KB Output is correct
9 Correct 2 ms 17844 KB Output is correct
10 Correct 2 ms 17844 KB Output is correct
11 Correct 2 ms 17844 KB Output is correct
12 Correct 2 ms 17844 KB Output is correct
13 Correct 2 ms 17844 KB Output is correct
14 Correct 2 ms 17844 KB Output is correct
15 Correct 2 ms 17844 KB Output is correct
16 Correct 2 ms 17844 KB Output is correct
17 Correct 2 ms 17844 KB Output is correct
18 Correct 2 ms 17844 KB Output is correct
19 Correct 2 ms 17844 KB Output is correct
20 Correct 2 ms 17844 KB Output is correct
21 Correct 2 ms 17844 KB Output is correct
22 Correct 2 ms 17844 KB Output is correct
23 Incorrect 2 ms 17844 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17844 KB Output is correct
2 Correct 2 ms 17844 KB Output is correct
3 Correct 2 ms 17844 KB Output is correct
4 Correct 2 ms 17844 KB Output is correct
5 Correct 2 ms 17844 KB Output is correct
6 Correct 2 ms 17844 KB Output is correct
7 Correct 2 ms 17844 KB Output is correct
8 Correct 2 ms 17844 KB Output is correct
9 Correct 2 ms 17844 KB Output is correct
10 Correct 2 ms 17844 KB Output is correct
11 Correct 2 ms 17844 KB Output is correct
12 Correct 2 ms 17844 KB Output is correct
13 Correct 2 ms 17844 KB Output is correct
14 Correct 2 ms 17844 KB Output is correct
15 Correct 2 ms 17844 KB Output is correct
16 Correct 2 ms 17844 KB Output is correct
17 Correct 2 ms 17844 KB Output is correct
18 Correct 2 ms 17844 KB Output is correct
19 Correct 2 ms 17844 KB Output is correct
20 Correct 2 ms 17844 KB Output is correct
21 Correct 2 ms 17844 KB Output is correct
22 Correct 2 ms 17844 KB Output is correct
23 Incorrect 2 ms 17844 KB Output isn't correct
24 Halted 0 ms 0 KB -