Submission #248378

#	Time	Username	Problem	Language	Result	Execution time	Memory
248378		lyc	Horses (IOI15_horses)	C++14	0 / 100	1593 ms	58364 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, px, my;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2), px(0), my(0) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

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

    void uy(int i, int v) {
        if (s == e) { my = v; return; }
        else if (i <= m) l->uy(i,v);
        else r->uy(i,v);
        my = max(l->my,r->my);
    }

    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;
    }

    int qy(int i, int j) {
        if (s == i && e == j) return my;
        if (j <= m) return l->qy(i,j);
        if (i > m) return r->qy(i,j);
        return max(l->qy(i,m),r->qy(m+1,j));
    }

    ii qlxy(int i, int j) {
        if (s == e) return ii(px>1?s:-1,my);
        if (j <= m) return l->qlxy(i,j);
        if (i > m) return r->qlxy(i,j);

        if (qx(m+1,j) > 1) return r->qlxy(m+1,j);
        ii a = qlxy(i,m);
        a.second = max(a.second,r->qy(m+1,j));
        return a;
    }
} *root;

int calc() {
    int j = N, gj = N, cy = 0;
    ll px = 0;
    FOR(i,1,31){
        ii r = root->qlxy(0,j-1);
        if (r.first == -1) break;
        j = r.first;
        if (r.second > 1LL*cy*px) {
            gj = j;
            cy = r.second;
            px = X[r.first];
        } else {
            px *= X[r.first];
            if (px > 1e9) break;
        }
        if (j == 0) break;
    }
	return 1LL * root->qx(0,gj) * cy % 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->uy(i,Y[i]);
    }
    return calc();
}

int updateX(int pos, int val) {	
    root->ux(pos,val);
    return calc();
}

int updateY(int pos, int val) {
    root->uy(pos,val);
	return calc();
}

Compilation message (stderr)

horses.cpp: In constructor 'node::node(int, int)':
horses.cpp:22: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), my(0) {
                       ^
horses.cpp:20:12: note: shadowed declaration is here
     int s, e, m, px, my;
            ^
horses.cpp:22: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), my(0) {
                       ^
horses.cpp:20:9: note: shadowed declaration is here
     int s, e, m, px, my;
         ^
horses.cpp: In member function 'void node::ux(int, int)':
horses.cpp:33: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:47: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:82:22: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
             if (px > 1e9) break;
                      ^~~
horses.cpp:86:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * root->qx(0,gj) * cy % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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