oj.uz

Submission #77406

# Submission time Handle Problem Language Result Execution time Memory
77406 2018-09-27T14:48:38 Z MvC Horses (IOI15_horses) C++14
37 / 100
 477 ms 67344 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 = y[*it];
        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 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 2 ms 776 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 2 ms 884 KB Output is correct
8 Correct 2 ms 884 KB Output is correct
9 Correct 2 ms 884 KB Output is correct
10 Correct 2 ms 884 KB Output is correct
11 Correct 2 ms 884 KB Output is correct
12 Correct 2 ms 888 KB Output is correct
13 Correct 2 ms 892 KB Output is correct
14 Correct 2 ms 896 KB Output is correct
15 Correct 2 ms 900 KB Output is correct
16 Correct 2 ms 912 KB Output is correct
17 Correct 2 ms 916 KB Output is correct
18 Correct 2 ms 920 KB Output is correct
19 Correct 2 ms 924 KB Output is correct
20 Correct 2 ms 936 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Output is correct
2 Correct 2 ms 1088 KB Output is correct
3 Correct 2 ms 1088 KB Output is correct
4 Correct 2 ms 1092 KB Output is correct
5 Correct 2 ms 1096 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1104 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 1120 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 1276 KB Output is correct
20 Correct 2 ms 1276 KB Output is correct
21 Correct 2 ms 1276 KB Output is correct
22 Incorrect 2 ms 1276 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 43288 KB Output is correct
2 Correct 431 ms 55864 KB Output is correct
3 Correct 392 ms 59616 KB Output is correct
4 Correct 477 ms 67344 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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