Submission #107551

#	Time	Username	Problem	Language	Result	Execution time	Memory
107551		PeppaPig	Horses (IOI15_horses)	C++14	100 / 100	409 ms	50808 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
 
#define long long long
 
using namespace std;
 
const int N = 1<<19;
const int M = 1e9+7;
 
#define var int p = 1, int l = 0, int r = n-1
#define mid ((l + r) >> 1)
#define lb p<<1, l, mid
#define rb p<<1|1, mid+1, r
 
struct node {
    double log;
    long sum;
    node() : log(0), sum(1) { }
    node(double log, long sum) : log(log), sum(sum) { }
    friend node operator+(const node &a, const node &b) {
        node ret;
        ret.log = a.log + b.log;
        ret.sum = (a.sum * b.sum) % M;
        return ret;
    }
    friend bool operator<(const node &a, const node &b) {
        return make_pair(a.log, a.sum) < make_pair(b.log, b.sum);
    }
} t[N<<1], lz[N<<1];
 
int n, x[N], y[N];
node A[N];
 
void build(var) {
    if(l == r) return void(t[p] = A[l]);
    build(lb), build(rb);
    t[p] = t[p<<1] < t[p<<1|1] ? t[p<<1|1] : t[p<<1];
}
 
void push(var) {
    t[p] = t[p] + lz[p];
    if(l != r) {
        lz[p<<1] = lz[p<<1] + lz[p];
        lz[p<<1|1] = lz[p<<1|1] + lz[p];
    }
    lz[p] = node(0, 1);
}
 
void update(int x, int y, node k, var) {
    push(p, l, r);
    if(x > r || l > y) return;
    if(x <= l && r <= y) {
        lz[p] = lz[p] + k;
        push(p, l, r);
        return;
    }
    update(x, y, k, lb), update(x, y, k, rb);
    t[p] = t[p<<1] < t[p<<1|1] ? t[p<<1|1] : t[p<<1];
}
 
int init(int N, int X[], int Y[]) {
    n = N;
    node cul(0, 1);
    for(int i = 0; i < n; i++) {
        x[i] = X[i], y[i] = Y[i];
        cul = cul + node((double)log2(x[i]), x[i]);
        A[i] = cul + node((double)log2(y[i]), y[i]); 
    }
    build();
    return t[1].sum;
}
 
long modpow(long a, long b) {
    long ret = 1;
    for( ; b; b >>= 1) {
        if(b & 1) ret = (ret * a) % M;
        a = (a * a) % M;
    }
    return ret;
}
 
int updateX(int pos, int val) {
    double nlog = (double)log2(val) - (double)log2(x[pos]);
    long nsum = (1ll * val * modpow(x[pos], M-2)) % M;
    x[pos] = val;
    update(pos, n-1, node(nlog, nsum));
    return t[1].sum;
}
 
int updateY(int pos, int val) {
    double nlog = (double)log2(val) - (double)log2(y[pos]);
    long nsum = (1ll * val * modpow(y[pos], M-2)) % M;
    y[pos] = val;
    update(pos, pos, node(nlog, nsum));
    return t[1].sum;
}

Compilation message (stderr)

horses.cpp: In constructor 'node::node(double, long long int)':
horses.cpp:20:32: warning: declaration of 'sum' shadows a member of 'node' [-Wshadow]
     node(double log, long sum) : log(log), sum(sum) { }
                                ^
horses.cpp:18:10: note: shadowed declaration is here
     long sum;
          ^~~
horses.cpp:20:32: warning: declaration of 'log' shadows a member of 'node' [-Wshadow]
     node(double log, long sum) : log(log), sum(sum) { }
                                ^
horses.cpp:17:12: note: shadowed declaration is here
     double log;
            ^~~
horses.cpp: In function 'void update(int, int, node, int, int, int)':
horses.cpp:50:38: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void update(int x, int y, node k, var) {
                                      ^
horses.cpp:32:14: note: shadowed declaration is here
 int n, x[N], y[N];
              ^
horses.cpp:50:38: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(int x, int y, node k, var) {
                                      ^
horses.cpp:32:8: note: shadowed declaration is here
 int n, x[N], y[N];
        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:62:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:8:11: note: shadowed declaration is here
 const int N = 1<<19;
           ^
horses.cpp:71:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return t[1].sum;
            ~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return t[1].sum;
            ~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:96:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return t[1].sum;
            ~~~~~^~~

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