Submission #77406

#	Time	Username	Problem	Language	Result	Execution time	Memory
77406		MvC	Horses (IOI15_horses)	C++14	37 / 100	477 ms	67344 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23