Submission #639004

#	Time	Username	Problem	Language	Result	Execution time	Memory
639004		ghostwriter	Horses (IOI15_horses)	C++14	100 / 100	174 ms	46332 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int oo = 1e9 + 1;
const int M = 1e9 + 7;
const int MAXN = 5e5 + 1;
const int MAXT = 2e6 + 1;
struct Node {
	int pre, suf, x, y, pos, val;
	Node() {}
	Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
};
int comp(ll x) { return min(x, 1LL * oo); }
Node comb(Node &a, Node &b) {
	Node ans;
	int newy = comp(1LL * comp(1LL * comp(1LL * a.suf * b.pre) * b.x) * b.y);
	if (a.y < newy) {
		ans.pre = comp(1LL * a.val * b.pre);
		ans.suf = b.suf;
		ans.x = b.x;
		ans.y = b.y;
		ans.pos = b.pos;
	}
	else {
		ans.pre = a.pre;
		ans.suf = comp(1LL * a.suf * b.val);
		ans.x = a.x;
		ans.y = a.y;
		ans.pos = a.pos;
	}
	ans.val = 1LL * a.val * b.val % M;
	return ans;
}
int N;
Node tr[MAXT];
pi a[MAXN];
void build(int i, int l, int r) {
	if (l == r) {
		tr[i] = Node(1, 1, a[l].st, a[l].nd, l, a[l].st);
		return;
	}
	int mid = l + (r - l) / 2;
	build(i * 2, l, mid);
	build(i * 2 + 1, mid + 1, r);
	tr[i] = comb(tr[i * 2], tr[i * 2 + 1]);
}
void upd(int i, int l, int r, int q) {
	if (r < q || l > q) return;
	if (l == r) {
		tr[i] = Node(1, 1, a[l].st, a[l].nd, l, a[l].st);
		return;
	}
	int mid = l + (r - l) / 2;
	upd(i * 2, l, mid, q);
	upd(i * 2 + 1, mid + 1, r, q);
	tr[i] = comb(tr[i * 2], tr[i * 2 + 1]);
}
int get(int i, int l, int r, int ql, int qr) {
	if (r < ql || l > qr) return 1;
	if (ql <= l && r <= qr) return tr[i].val;
	int mid = l + (r - l) / 2;
	return 1LL * get(i * 2, l, mid, ql, qr) * get(i * 2 + 1, mid + 1, r, ql, qr) % M;
}
int init(int N, int X[], int Y[]) {
	::N = N;
	FOR(i, 0, N - 1) a[i] = {X[i], Y[i]};
	build(1, 0, N - 1);
	int pos = tr[1].pos;
	return 1LL * get(1, 0, N - 1, 0, pos) * a[pos].nd % M;
}
int updateX(int pos, int val) {
	a[pos].st = val;
	upd(1, 0, N - 1, pos);
	int pos1 = tr[1].pos;
	return 1LL * get(1, 0, N - 1, 0, pos1) * a[pos1].nd % M;
}
int updateY(int pos, int val) {
	a[pos].nd = val;
	upd(1, 0, N - 1, pos);
	int pos1 = tr[1].pos;
	return 1LL * get(1, 0, N - 1, 0, pos1) * a[pos1].nd % M;
}

Compilation message (stderr)

horses.cpp: In constructor 'Node::Node(int, int, int, int, int, int)':
horses.cpp:45:52: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                                ~~~~^~~
horses.cpp:43:27: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                           ^~~
horses.cpp:45:43: warning: declaration of 'pos' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                       ~~~~^~~
horses.cpp:43:22: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                      ^~~
horses.cpp:45:36: warning: declaration of 'y' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                ~~~~^
horses.cpp:43:19: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                   ^
horses.cpp:45:29: warning: declaration of 'x' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                         ~~~~^
horses.cpp:43:16: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                ^
horses.cpp:45:20: warning: declaration of 'suf' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                ~~~~^~~
horses.cpp:43:11: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |           ^~~
horses.cpp:45:11: warning: declaration of 'pre' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |       ~~~~^~~
horses.cpp:43:6: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |      ^~~
horses.cpp: In constructor 'Node::Node(int, int, int, int, int, int)':
horses.cpp:45:52: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                                ~~~~^~~
horses.cpp:43:27: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                           ^~~
horses.cpp:45:43: warning: declaration of 'pos' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                       ~~~~^~~
horses.cpp:43:22: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                      ^~~
horses.cpp:45:36: warning: declaration of 'y' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                ~~~~^
horses.cpp:43:19: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                   ^
horses.cpp:45:29: warning: declaration of 'x' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                         ~~~~^
horses.cpp:43:16: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                ^
horses.cpp:45:20: warning: declaration of 'suf' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                ~~~~^~~
horses.cpp:43:11: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |           ^~~
horses.cpp:45:11: warning: declaration of 'pre' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |       ~~~~^~~
horses.cpp:43:6: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |      ^~~
horses.cpp: In constructor 'Node::Node(int, int, int, int, int, int)':
horses.cpp:45:52: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                                ~~~~^~~
horses.cpp:43:27: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                           ^~~
horses.cpp:45:43: warning: declaration of 'pos' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                       ~~~~^~~
horses.cpp:43:22: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                      ^~~
horses.cpp:45:36: warning: declaration of 'y' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                                ~~~~^
horses.cpp:43:19: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                   ^
horses.cpp:45:29: warning: declaration of 'x' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                         ~~~~^
horses.cpp:43:16: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |                ^
horses.cpp:45:20: warning: declaration of 'suf' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |                ~~~~^~~
horses.cpp:43:11: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |           ^~~
horses.cpp:45:11: warning: declaration of 'pre' shadows a member of 'Node' [-Wshadow]
   45 |  Node(int pre, int suf, int x, int y, int pos, int val) : pre(pre), suf(suf), x(x), y(y), pos(pos), val(val) {}
      |       ~~~~^~~
horses.cpp:43:6: note: shadowed declaration is here
   43 |  int pre, suf, x, y, pos, val;
      |      ^~~
horses.cpp: In function 'int comp(ll)':
horses.cpp:47:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   47 | int comp(ll x) { return min(x, 1LL * oo); }
      |                         ~~~^~~~~~~~~~~~~
horses.cpp: In function 'Node comb(Node&, Node&)':
horses.cpp:65:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |  ans.val = 1LL * a.val * b.val % M;
      |            ~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:96:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return 1LL * get(i * 2, l, mid, ql, qr) * get(i * 2 + 1, mid + 1, r, ql, qr) % M;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   98 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:68:5: note: shadowed declaration is here
   68 | int N;
      |     ^
horses.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
horses.cpp:100:2: note: in expansion of macro 'FOR'
  100 |  FOR(i, 0, N - 1) a[i] = {X[i], Y[i]};
      |  ^~~
horses.cpp:103:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  return 1LL * get(1, 0, N - 1, 0, pos) * a[pos].nd % M;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  return 1LL * get(1, 0, N - 1, 0, pos1) * a[pos1].nd % M;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:115:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |  return 1LL * get(1, 0, N - 1, 0, pos1) * a[pos1].nd % M;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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