Submission #432492

#	Time	Username	Problem	Language	Result	Execution time	Memory
432492		balbit	말 (IOI15_horses)	C++14	100 / 100	443 ms	60880 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT


#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int )((x).size())
#define pb push_back

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

//signed main(){bug(1,2);}

const int maxn = 5e5+5;
const int mod = 1e9+7;

ll X[maxn], Y[maxn], s[maxn], seg[maxn*2];
int n;
ll inv(ll b) {
    return b == 1? 1 : inv(mod%b) * (mod - mod / b) % mod;
}

set<int> notone;
int QU(int e) {
    ll re = 1;
    for (++e; e>0; e-=e&-e) {
        re = re * s[e] % mod;
    }
    return re;
}

void MO(int e, ll v) {
    for (++e; e<maxn; e+=e&-e) {
        s[e] *= v; s[e] %= mod;
    }
}

ll cap = 1e9+10;

void modify(int p, int v) {
    p+=maxn;
//    bug(p,v);
    for (seg[p] = v; p>1; p>>=1) {
        seg[p>>1] = max(seg[p], seg[p^1]);
//        bug(seg[p>>1]);
    }
}

ll query(int l, int r) {
    ll re = 1;
    for (l+=maxn, r+=maxn; l<r; l>>=1, r>>=1) {
        if (l & 1) MX(re, seg[l++]);
        if (r & 1) MX(re, seg[--r]);
    }
    return re;
}

int get(){
    auto sit = prev(notone.end());
    ll bon = 1;
    ll nowbig = 0;
    int prv = n;
    while (1) {
        int i = *sit;
        MX(nowbig, query(i, prv)); // [,)
        bug(i, prv, query(i,prv));
        prv = i;
        nowbig *= X[i];
        bug(i, nowbig);
        if (sit == notone.begin() || nowbig > cap) break;
        --sit;
    }
    nowbig %= mod;
    return nowbig * QU(prv-1) % mod;
}

bool good(int i) {
    return i == 0 || X[i] != 1;
}

int init(int _n, int _X[], int _Y[]) {
    fill(s, s+maxn, 1);
    fill(seg, seg+maxn*2, 0);
    n = _n;
    REP(i,_n) {
        X[i] = _X[i]; Y[i] = _Y[i];
        MO(i, X[i]);
        modify(i, Y[i]);
        if (good(i)) notone.insert(i);
    }
	return get();
}

int updateX(int i, int val) {
    if (good(i)) notone.erase(i);
    MO(i, inv(X[i]));
    X[i] = val;
    if (good(i)) notone.insert(i);
    MO(i, (X[i]));
	return get();
}

int updateY(int pos, int val) {
    modify(pos, val);
	return get();
}

//signed main(){
//    bug(inv(2));
//}

Compilation message (stderr)

horses.cpp: In function 'int QU(int)':
horses.cpp:47:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 |     return re;
      |            ^~
horses.cpp: In function 'int get()':
horses.cpp:92:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |     return nowbig * QU(prv-1) % mod;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:78:8: warning: unused variable 'bon' [-Wunused-variable]
   78 |     ll bon = 1;
      |        ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:106:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |         modify(i, Y[i]);
      |                   ~~~^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23