Submission #248389

#	Time	Username	Problem	Language	Result	Execution time	Memory
248389		lyc	Horses (IOI15_horses)	C++14	100 / 100	1028 ms	115832 KiB

horses

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;
using ii=pair<int,int>;

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

int N, X[mxN], Y[mxN];

struct node {
    int s, e, m;
    int px, idx;
    long double v, lz;

    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2), px(0), idx(s), v(0), lz(0) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    long double val() {
        if (lz != 0) {
            v += lz;
            if (s != e) {
                l->lz += lz;
                r->lz += lz;
            }
            lz = 0;
        }
        return v;
    }

    void recalc() {
        if (l->val() > r->val()) v = l->val(), idx = l->idx;
        else v = r->val(), idx = r->idx;
    }

    void ux(int i, int x) {
        if (s == e) { px = x; return; }
        if (i <= m) l->ux(i,x);
        else r->ux(i,x);
        px = 1LL * l->px * r->px % mod;
    }

    void av(int i, double x) {
        if (s == e) { v += x; return; }
        else if (i <= m) l->av(i,x);
        else r->av(i,x);
        val();
        recalc();
    }

    void av(int i, int j, double x) {
        if (s == i && e == j) { lz += x; return; }
        if (j <= m) l->av(i,j,x);
        else if (i > m) r->av(i,j,x);
        else l->av(i,m,x), r->av(m+1,j,x);
        val();
        recalc();
    }

    int qx(int i, int j) {
        if (s == i && e == j) return px;
        if (j <= m) return l->qx(i,j);
        if (i > m) return r->qx(i,j);
        return 1LL * l->qx(i,m) * r->qx(m+1,j) % mod;
    }

    void dbg() {
        if (s == e) {
            cout << s << " :: " << px _ idx _ v _ lz << endl;
        } else l->dbg(), r->dbg();
    }
} *root;

int calc() { return 1LL * root->qx(0,root->idx) * Y[root->idx] % mod; }

int init(int _N, int _X[], int _Y[]) {
    N = _N;
    root = new node(0,N-1);
    FOR(i,0,N-1) {
        X[i] = _X[i], Y[i] = _Y[i];
        root->ux(i,X[i]);
        root->av(i,N-1,log10(X[i]));
        root->av(i,log10(Y[i]));
    }
    return calc();
}

int updateX(int pos, int val) {	
    root->av(pos,N-1,-log10(X[pos]));
    X[pos] = val;
    root->ux(pos,val);
    root->av(pos,N-1,log10(val));
    return calc();
}

int updateY(int pos, int val) {
    root->av(pos,-log10(Y[pos]));
    Y[pos] = val;
    root->av(pos,log10(val));
	return calc();
}

Compilation message (stderr)

horses.cpp: In constructor 'node::node(int, int)':
horses.cpp:25:23: warning: declaration of 'e' shadows a member of 'node' [-Wshadow]
     node(int s, int e): s(s), e(e), m((s+e)/2), px(0), idx(s), v(0), lz(0) {
                       ^
horses.cpp:20:12: note: shadowed declaration is here
     int s, e, m;
            ^
horses.cpp:25:23: warning: declaration of 's' shadows a member of 'node' [-Wshadow]
     node(int s, int e): s(s), e(e), m((s+e)/2), px(0), idx(s), v(0), lz(0) {
                       ^
horses.cpp:20:9: note: shadowed declaration is here
     int s, e, m;
         ^
horses.cpp: In member function 'void node::ux(int, int)':
horses.cpp:53:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         px = 1LL * l->px * r->px % mod;
              ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int node::qx(int, int)':
horses.cpp:77:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         return 1LL * l->qx(i,m) * r->qx(m+1,j) % mod;
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int calc()':
horses.cpp:87:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 int calc() { return 1LL * root->qx(0,root->idx) * Y[root->idx] % mod; }
                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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