Submission #670098

#	Time	Username	Problem	Language	Result	Execution time	Memory
670098		Astrayt	Horses (IOI15_horses)	C++17	100 / 100	733 ms	126168 KiB

horses

#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long
#define double long double
#define pii pair<int,int>
#define pb push_back
#define maxn 500005
#define mod 1000000007ll
#define ff first
#define ss second

int N;
vector<int> X, Y;
vector<double> lgX, lgY, PlgX;

int fastpow(int a, int b){
    int ret = 1;
    for(; b; b >>= 1){
        if(b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
    }
    return ret;
}

struct FenwickTree{
    int val[maxn];
    void init(int n){
        for(int i = 0; i <= n; ++i) val[i] = 1;
    }
    void modify(int p, int x){
        for(; p < maxn; p += (p & -p)) val[p] = 1ll * x * val[p] % mod;
    }
    int query(int p){
        int ret = 1;
        for(; p; p -= (p & -p)){
            ret = 1ll * ret * val[p] % mod;
        }
        return ret;
    }
}bit;

struct SegmentTree{
    pair<double, int> node[4 * maxn];
    double tag[4 * maxn];
    void push(int i){
        double t = tag[i];
        node[2 * i].ff += t, tag[2 * i] += t;
        node[2 * i + 1].ff += t, tag[2 * i + 1] += t;
        tag[i] = 0;
        node[i] = max(node[2 * i], node[2 * i + 1]);
    }
    void modify(int i, int l, int r, int ql, int qr, double x){
        if(l == r){
            node[i].ff += x;
            node[i].ss = l;
            return;
        }
        push(i);
        if(ql <= l && r <= qr){
            node[i].ff += x;
            tag[i] += x;
            return;
        }
        int mid = (l + r) / 2;
        if(ql <= mid) modify(2 * i, l, mid, ql, qr, x);
        if(mid < qr) modify(2 * i + 1, mid + 1, r, ql, qr, x);
        node[i] = max(node[2 * i], node[2 * i + 1]);
    }
}seg;

int init(int n, int *x, int *y){
    N = n;
    bit.init(N + 1);
    X.assign(N + 1, 0), Y.assign(N + 1, 0);
    lgX.assign(N + 1, 0.0), lgY.assign(N + 1, 0.0), PlgX.assign(N + 1, 0.0);
    for(int i = 1; i <= n; ++i){
        X[i] = x[i - 1], Y[i] = y[i - 1];
        lgX[i] = log(X[i]), lgY[i] = log(Y[i]);
        PlgX[i] = PlgX[i - 1] + lgX[i];
        bit.modify(i, X[i]);
        seg.modify(1, 1, N, i, i, PlgX[i] + lgY[i]);
    }
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

int updateX(int pos, int val){
    pos++;
    bit.modify(pos, fastpow(X[pos], mod - 2));
    bit.modify(pos, val);
    seg.modify(1, 1, N, pos, N, -lgX[pos]);
    X[pos] = val;
    lgX[pos] = log(val);
    seg.modify(1, 1, N, pos, N, lgX[pos]);
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

int updateY(int pos, int val){
    pos++;
    seg.modify(1, 1, N, pos, pos, -lgY[pos]);
    Y[pos] = val;
    lgY[pos] = log(val);
    seg.modify(1, 1, N, pos, pos, lgY[pos]);
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

Compilation message (stderr)

horses.cpp: In function 'int fastpow(int, int)':
horses.cpp:20:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |         if(b & 1) ret = 1ll * ret * a % mod;
      |                                       ^
horses.cpp:21:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |         a = 1ll * a * a % mod;
      |                         ^
horses.cpp: In member function 'void FenwickTree::modify(int, int)':
horses.cpp:32:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |         for(; p < maxn; p += (p & -p)) val[p] = 1ll * x * val[p] % mod;
      |                                                                  ^
horses.cpp: In member function 'int FenwickTree::query(int)':
horses.cpp:37:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |             ret = 1ll * ret * val[p] % mod;
      |                                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:86:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |     return 1ll * BX * Y[id] % mod;
      |                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:99:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |     return 1ll * BX * Y[id] % mod;
      |                             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:110:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |     return 1ll * BX * Y[id] % mod;
      |                             ^

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