Submission #41874

#	Time	Username	Problem	Language	Result	Execution time	Memory
41874		funcsr	Horses (IOI15_horses)	C++14	100 / 100	376 ms	263672 KiB

horses

#include "horses.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007

struct Node {
  int b, ans, l, r, p;
  Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
  Node () : b(0), ans(0), l(1), r(1), p(1) {}
};
inline int prod(int x, int y) { return min(1LL*x*y, (long long)INF); }
Node op(const Node &x, const Node &y) {
  if (x.b < prod(prod(y.l, x.r), y.b)) {
    return Node(y.b, (1LL*x.p*y.ans)%MOD, prod(prod(x.l, x.r), y.l), y.r, (1LL*x.p*y.p)%MOD);
  }
  else {
    return Node(x.b, x.ans, x.l, prod(x.r, prod(y.l, y.r)), (1LL*x.p*y.p)%MOD);
  }
}
#define MAX_N (1<<19)
Node seg[MAX_N*2-1];
void update(int k, Node v) {
  k += MAX_N-1;
  seg[k] = v;
  while (k > 0) {
    k = (k-1)/2;
    seg[k] = op(seg[k*2+1], seg[k*2+2]);
  }
}

int N;
int X[500000], Y[500000];
int init(int NN, int XX[], int YY[]) {
  N = NN;
  rep(i, N) X[i] = XX[i], Y[i] = YY[i];
  rep(i, N) update(i, Node(Y[i], (1LL*X[i]*Y[i])%MOD, X[i], 1, X[i]));
  return seg[0].ans;
}

int updateX(int pos, int val) {
  X[pos] = val;
  update(pos, Node(Y[pos], (1LL*X[pos]*Y[pos])%MOD, X[pos], 1, X[pos]));
  return seg[0].ans;
}

int updateY(int pos, int val) {
  Y[pos] = val;
  update(pos, Node(Y[pos], (1LL*X[pos]*Y[pos])%MOD, X[pos], 1, X[pos]));
  return seg[0].ans;
}

Compilation message (stderr)

horses.cpp: In constructor 'Node::Node(int, int, int, int, int)':
horses.cpp:17:46: warning: declaration of 'p' shadows a member of 'Node' [-Wshadow]
   Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
                                              ^
horses.cpp:16:21: note: shadowed declaration is here
   int b, ans, l, r, p;
                     ^
horses.cpp:17:46: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
                                              ^
horses.cpp:16:18: note: shadowed declaration is here
   int b, ans, l, r, p;
                  ^
horses.cpp:17:46: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
                                              ^
horses.cpp:16:15: note: shadowed declaration is here
   int b, ans, l, r, p;
               ^
horses.cpp:17:46: warning: declaration of 'ans' shadows a member of 'Node' [-Wshadow]
   Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
                                              ^
horses.cpp:16:10: note: shadowed declaration is here
   int b, ans, l, r, p;
          ^
horses.cpp:17:46: warning: declaration of 'b' shadows a member of 'Node' [-Wshadow]
   Node (int b, int ans, int l, int r, int p) : b(b), ans(ans), l(l), r(r), p(p) {}
                                              ^
horses.cpp:16:7: note: shadowed declaration is here
   int b, ans, l, r, p;
       ^
horses.cpp: In function 'int prod(int, int)':
horses.cpp:20:67: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 inline int prod(int x, int y) { return min(1LL*x*y, (long long)INF); }
                                                                   ^
horses.cpp: In function 'Node op(const Node&, const Node&)':
horses.cpp:23:92: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return Node(y.b, (1LL*x.p*y.ans)%MOD, prod(prod(x.l, x.r), y.l), y.r, (1LL*x.p*y.p)%MOD);
                                                                                            ^
horses.cpp:23:92: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
horses.cpp:26:78: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return Node(x.b, x.ans, x.l, prod(x.r, prod(y.l, y.r)), (1LL*x.p*y.p)%MOD);
                                                                              ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:45:68: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   rep(i, N) update(i, Node(Y[i], (1LL*X[i]*Y[i])%MOD, X[i], 1, X[i]));
                                                                    ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:51:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   update(pos, Node(Y[pos], (1LL*X[pos]*Y[pos])%MOD, X[pos], 1, X[pos]));
                                                                      ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:57:70: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   update(pos, Node(Y[pos], (1LL*X[pos]*Y[pos])%MOD, X[pos], 1, X[pos]));
                                                                      ^

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