oj.uz

Submission #74339

# Submission time Handle Problem Language Result Execution time Memory
74339 2018-08-31T10:50:52 Z imeimi2000 Horses (IOI15_horses) C++14
100 / 100
 704 ms 276804 KB 
#include "horses.h"
#include <set>

using namespace std;
typedef long long llong;

int n;
int x[500001];
int y[500001];

set<int> mp;
int seg[1 << 20];

void initSeg(int i, int s, int e) {
    if (s == e) {
        seg[i] = y[s];
        return;
    }
    int m = (s + e) / 2;
    initSeg(i << 1, s, m);
    initSeg(i << 1 | 1, m + 1, e);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

void update(int i, int s, int e, int x) {
    if (s == e) {
        seg[i] = y[x];
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x);
    else update(i << 1 | 1, m + 1, e, x);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

int query(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return 0;
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(query(i << 1, s, m, x, y), query(i << 1 | 1, m + 1, e, x, y));
}

const int mod = 1e9 + 7;

int pw(int x, int p) {
    int ret = 1;
    while (p) {
        if (p & 1) ret = (llong)ret * x % mod;
        x = (llong)x * x % mod;
        p >>= 1;
    }
    return ret;
}
int fen[500001];
void init() {
    for (int i = 1; i <= n; ++i) fen[i] = x[i];
    for (int i = 1; i <= n; ++i) {
        int j = i + (i & -i);
        if (j <= n) fen[j] = (llong)fen[j] * fen[i] % mod;
    }
}

void update(int i, int x) {
    while (i <= n) {
        fen[i] = (llong)fen[i] * x % mod;
        i += i & -i;
    }
}

int query(int i) {
    int ret = 1;
    while (i) {
        ret = (llong)ret * fen[i] % mod;
        i -= i & -i;
    }
    return ret;
}

int get() {
    int mxi;
    llong mxv = 0;
    mp.insert(1);
    set<int>::iterator it = mp.end();
    for (int loop = 0; loop < 35 && it != mp.begin(); ++loop) {
        --it;
        int mxY = query(1, 1, n, *it, n);
        if (mxv < mxY) {
            mxi = *it;
            mxv = mxY;
        }
        mxv *= x[*it];
        if (mod < mxv) break;
    }
    return (llong)query(mxi) * query(1, 1, n, mxi, n) % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 1; i <= n; ++i) {
        x[i] = X[i - 1]; y[i] = Y[i - 1];
        if (x[i] > 1) mp.insert(i);
	}
	init();
	initSeg(1, 1, n);
	return get();
}

int updateX(int pos, int val) {
    ++pos;
    update(pos, (llong)val * pw(x[pos], mod - 2) % mod);
    if (x[pos] > 1) mp.erase(pos);
    x[pos] = val;
    if (x[pos] > 1) mp.insert(pos);
	return get();
}

int updateY(int pos, int val) {
    ++pos;
    y[pos] = val;
    update(1, 1, n, pos);
	return get();
}

Compilation message

horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:25:39: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(int i, int s, int e, int x) {
                                       ^
horses.cpp:8:5: note: shadowed declaration is here
 int x[500001];
     ^
horses.cpp: In function 'int query(int, int, int, int, int)':
horses.cpp:36:44: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 int query(int i, int s, int e, int x, int y) {
                                            ^
horses.cpp:9:5: note: shadowed declaration is here
 int y[500001];
     ^
horses.cpp:36:44: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int query(int i, int s, int e, int x, int y) {
                                            ^
horses.cpp:8:5: note: shadowed declaration is here
 int x[500001];
     ^
horses.cpp: In function 'int pw(int, int)':
horses.cpp:45:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int pw(int x, int p) {
                    ^
horses.cpp:8:5: note: shadowed declaration is here
 int x[500001];
     ^
horses.cpp:48:41: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
         if (p & 1) ret = (llong)ret * x % mod;
                          ~~~~~~~~~~~~~~~^~~~~
horses.cpp:49:26: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
         x = (llong)x * x % mod;
             ~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void init()':
horses.cpp:59:53: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
         if (j <= n) fen[j] = (llong)fen[j] * fen[i] % mod;
                              ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(int, int)':
horses.cpp:63:25: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(int i, int x) {
                         ^
horses.cpp:8:5: note: shadowed declaration is here
 int x[500001];
     ^
horses.cpp:65:36: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
         fen[i] = (llong)fen[i] * x % mod;
                  ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int query(int)':
horses.cpp:73:35: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
         ret = (llong)ret * fen[i] % mod;
               ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:94:55: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
     return (llong)query(mxi) * query(1, 1, n, mxi, n) % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:50: warning: conversion to 'int' from 'llong {aka long long int}' may alter its value [-Wconversion]
     update(pos, (llong)val * pw(x[pos], mod - 2) % mod);
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:94:37: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return (llong)query(mxi) * query(1, 1, n, mxi, n) % mod;
                                ~~~~~^~~~~~~~~~~~~~~~~

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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 2 ms 476 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 572 KB Output is correct
12 Correct 2 ms 576 KB Output is correct
13 Correct 2 ms 580 KB Output is correct
14 Correct 2 ms 584 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 608 KB Output is correct
18 Correct 2 ms 628 KB Output is correct
19 Correct 2 ms 632 KB Output is correct
20 Correct 2 ms 696 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 43176 KB Output is correct
2 Correct 479 ms 55936 KB Output is correct
3 Correct 483 ms 59680 KB Output is correct
4 Correct 508 ms 67356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 67356 KB Output is correct
2 Correct 2 ms 67356 KB Output is correct
3 Correct 2 ms 67356 KB Output is correct
4 Correct 2 ms 67356 KB Output is correct
5 Correct 2 ms 67356 KB Output is correct
6 Correct 2 ms 67356 KB Output is correct
7 Correct 2 ms 67356 KB Output is correct
8 Correct 2 ms 67356 KB Output is correct
9 Correct 2 ms 67356 KB Output is correct
10 Correct 2 ms 67356 KB Output is correct
11 Correct 2 ms 67356 KB Output is correct
12 Correct 2 ms 67356 KB Output is correct
13 Correct 2 ms 67356 KB Output is correct
14 Correct 2 ms 67356 KB Output is correct
15 Correct 2 ms 67356 KB Output is correct
16 Correct 2 ms 67356 KB Output is correct
17 Correct 2 ms 67356 KB Output is correct
18 Correct 2 ms 67356 KB Output is correct
19 Correct 2 ms 67356 KB Output is correct
20 Correct 2 ms 67356 KB Output is correct
21 Correct 2 ms 67356 KB Output is correct
22 Correct 2 ms 67356 KB Output is correct
23 Correct 2 ms 67356 KB Output is correct
24 Correct 3 ms 67356 KB Output is correct
25 Correct 4 ms 67356 KB Output is correct
26 Correct 3 ms 67356 KB Output is correct
27 Correct 4 ms 67356 KB Output is correct
28 Correct 3 ms 67356 KB Output is correct
29 Correct 3 ms 67356 KB Output is correct
30 Correct 4 ms 67356 KB Output is correct
31 Correct 4 ms 67356 KB Output is correct
32 Correct 4 ms 67356 KB Output is correct
33 Correct 47 ms 67356 KB Output is correct
34 Correct 44 ms 67356 KB Output is correct
35 Correct 276 ms 85396 KB Output is correct
36 Correct 285 ms 96188 KB Output is correct
37 Correct 77 ms 96188 KB Output is correct
38 Correct 160 ms 96188 KB Output is correct
39 Correct 35 ms 96188 KB Output is correct
40 Correct 268 ms 109212 KB Output is correct
41 Correct 60 ms 109212 KB Output is correct
42 Correct 79 ms 109212 KB Output is correct
43 Correct 251 ms 119776 KB Output is correct
44 Correct 240 ms 126076 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 126076 KB Output is correct
2 Correct 2 ms 126076 KB Output is correct
3 Correct 2 ms 126076 KB Output is correct
4 Correct 2 ms 126076 KB Output is correct
5 Correct 2 ms 126076 KB Output is correct
6 Correct 2 ms 126076 KB Output is correct
7 Correct 2 ms 126076 KB Output is correct
8 Correct 2 ms 126076 KB Output is correct
9 Correct 2 ms 126076 KB Output is correct
10 Correct 2 ms 126076 KB Output is correct
11 Correct 2 ms 126076 KB Output is correct
12 Correct 2 ms 126076 KB Output is correct
13 Correct 2 ms 126076 KB Output is correct
14 Correct 2 ms 126076 KB Output is correct
15 Correct 2 ms 126076 KB Output is correct
16 Correct 2 ms 126076 KB Output is correct
17 Correct 2 ms 126076 KB Output is correct
18 Correct 2 ms 126076 KB Output is correct
19 Correct 2 ms 126076 KB Output is correct
20 Correct 2 ms 126076 KB Output is correct
21 Correct 2 ms 126076 KB Output is correct
22 Correct 2 ms 126076 KB Output is correct
23 Correct 2 ms 126076 KB Output is correct
24 Correct 3 ms 126076 KB Output is correct
25 Correct 3 ms 126076 KB Output is correct
26 Correct 3 ms 126076 KB Output is correct
27 Correct 5 ms 126076 KB Output is correct
28 Correct 3 ms 126076 KB Output is correct
29 Correct 2 ms 126076 KB Output is correct
30 Correct 3 ms 126076 KB Output is correct
31 Correct 4 ms 126076 KB Output is correct
32 Correct 4 ms 126076 KB Output is correct
33 Correct 669 ms 131156 KB Output is correct
34 Correct 441 ms 144064 KB Output is correct
35 Correct 510 ms 147588 KB Output is correct
36 Correct 496 ms 155332 KB Output is correct
37 Correct 58 ms 155332 KB Output is correct
38 Correct 44 ms 155332 KB Output is correct
39 Correct 303 ms 173176 KB Output is correct
40 Correct 262 ms 183916 KB Output is correct
41 Correct 81 ms 183916 KB Output is correct
42 Correct 160 ms 183916 KB Output is correct
43 Correct 37 ms 183916 KB Output is correct
44 Correct 256 ms 196996 KB Output is correct
45 Correct 65 ms 196996 KB Output is correct
46 Correct 76 ms 196996 KB Output is correct
47 Correct 266 ms 207336 KB Output is correct
48 Correct 254 ms 213848 KB Output is correct
49 Correct 192 ms 213848 KB Output is correct
50 Correct 150 ms 213848 KB Output is correct
51 Correct 482 ms 236756 KB Output is correct
52 Correct 381 ms 248352 KB Output is correct
53 Correct 575 ms 248352 KB Output is correct
54 Correct 342 ms 248352 KB Output is correct
55 Correct 132 ms 248352 KB Output is correct
56 Correct 361 ms 265320 KB Output is correct
57 Correct 362 ms 265320 KB Output is correct
58 Correct 527 ms 265320 KB Output is correct
59 Correct 256 ms 276804 KB Output is correct