oj.uz

Submission #54714

# Submission time Handle Problem Language Result Execution time Memory
54714 2018-07-04T18:08:04 Z aome Horses (IOI15_horses) C++17
17 / 100
 344 ms 70736 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int mod = 1e9 + 7;

int n;
int x[N], y[N];
long double val[N];

struct SegmentTree {
	struct Node {
		int pos;
		long double val, lazy; 
	};

	Node T1[4 * N];
	int T2[4 * N];

	#define mid ((l + r) >> 1)

	Node merge(Node &x, Node &y) {
		Node z;
		if (x.val > y.val) {
			z.pos = x.pos, z.val = x.val; 
		}
		else {
			z.pos = y.pos, z.val = y.val;
		}
		return z;
	}

	void build(int i, int l, int r) {
		if (l == r) {
			T1[i].pos = l, T2[i] = x[l];
			T1[i].val = val[l], T1[i].lazy = 0;
			return;
		}
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
		T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
	}

	void push(int i, int l, int r) {
		T1[i].val += T1[i].lazy;
		if (l != r) {
			T1[i << 1].lazy += T1[i].lazy;
			T1[i << 1 | 1].lazy += T1[i].lazy;
		}
		T1[i].lazy = 0;
	}

	void updX(int i, int l, int r, int L, int R, long double v) {
		push(i, l, r);
		if (L > r || l > R) return;
		if (L <= l && r <= R) {
			T1[i].lazy = v, push(i, l, r); return;
		}
		updX(i << 1, l, mid, L, R, v);
		updX(i << 1 | 1, mid + 1, r, L, R, v);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
	}

	void updY(int i, int l, int r, int p, int v) {
		push(i, l, r);
		if (l == r) {
			T1[i].val += log(v) - log(y[p]), y[p] = v;
			return;
		}
		if (mid >= p) updY(i << 1, l, mid, p, v);
		else updY(i << 1 | 1, mid + 1, r, p, v);
		T1[i] = merge(T1[i << 1], T1[i << 1 | 1]);
	}

	void updPrd(int i, int l, int r, int p, int v) {
		if (l == r) {
			T2[i] = x[p] = v; return; 
		}
		if (mid >= p) updPrd(i << 1, l, mid, p, v);
		else updPrd(i << 1 | 1, mid + 1, r, p, v);
		T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
	}

	int getPrd(int i, int l, int r, int L, int R) {
		if (l > R || L > r) return 1;
		if (L <= l && r <= R) return T2[i];
		return 1LL * getPrd(i << 1, l, mid, L, R) * getPrd(i << 1 | 1, mid + 1, r, L, R) % mod;
	}

	#undef mid

} IT;

int init(int _n, int _x[], int _y[]) {
	n = _n;
	for (int i = 0; i < n; ++i) {
		x[i] = _x[i], y[i] = _y[i];
	}
	val[0] = log(x[0]);
	for (int i = 1; i < n; ++i) {
		val[i] = val[i - 1] + log(x[i]);
	}
	for (int i = 0; i < n; ++i) {
		val[i] += log(y[i]);
	}
	IT.build(1, 0, n - 1);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

int updateX(int pos, int val) {
	IT.updX(1, 0, n - 1, pos, n - 1, log(val) - log(x[pos]));
	IT.updPrd(1, 0, n - 1, pos, val);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

int updateY(int pos, int val) {
	IT.updY(1, 0, n - 1, pos, val);
	int opt = IT.T1[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

Compilation message

horses.cpp: In member function 'SegmentTree::Node SegmentTree::merge(SegmentTree::Node&, SegmentTree::Node&)':
horses.cpp:25:31: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  Node merge(Node &x, Node &y) {
                               ^
horses.cpp:11:11: note: shadowed declaration is here
 int x[N], y[N];
           ^
horses.cpp:25:31: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  Node merge(Node &x, Node &y) {
                               ^
horses.cpp:11:5: note: shadowed declaration is here
 int x[N], y[N];
     ^
horses.cpp: In member function 'void SegmentTree::build(int, int, int)':
horses.cpp:45:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void SegmentTree::updPrd(int, int, int, int, int)':
horses.cpp:85:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   T2[i] = 1LL * T2[i << 1] * T2[i << 1 | 1] % mod;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int SegmentTree::getPrd(int, int, int, int, int)':
horses.cpp:91:84: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return 1LL * getPrd(i << 1, l, mid, L, R) * getPrd(i << 1 | 1, mid + 1, r, L, R) % mod;
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:112:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:12:13: note: shadowed declaration is here
 long double val[N];
             ^~~
horses.cpp:119:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:12:13: note: shadowed declaration is here
 long double val[N];
             ^~~
horses.cpp:125:55: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Correct 2 ms 760 KB Output is correct
23 Incorrect 3 ms 764 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 70580 KB Output is correct
2 Incorrect 344 ms 70736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 70736 KB Output is correct
2 Correct 2 ms 70736 KB Output is correct
3 Correct 2 ms 70736 KB Output is correct
4 Correct 2 ms 70736 KB Output is correct
5 Correct 2 ms 70736 KB Output is correct
6 Correct 2 ms 70736 KB Output is correct
7 Correct 2 ms 70736 KB Output is correct
8 Correct 2 ms 70736 KB Output is correct
9 Correct 2 ms 70736 KB Output is correct
10 Correct 2 ms 70736 KB Output is correct
11 Correct 2 ms 70736 KB Output is correct
12 Correct 2 ms 70736 KB Output is correct
13 Correct 2 ms 70736 KB Output is correct
14 Correct 2 ms 70736 KB Output is correct
15 Correct 2 ms 70736 KB Output is correct
16 Correct 2 ms 70736 KB Output is correct
17 Correct 3 ms 70736 KB Output is correct
18 Correct 2 ms 70736 KB Output is correct
19 Correct 2 ms 70736 KB Output is correct
20 Correct 3 ms 70736 KB Output is correct
21 Correct 3 ms 70736 KB Output is correct
22 Correct 3 ms 70736 KB Output is correct
23 Incorrect 4 ms 70736 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 70736 KB Output is correct
2 Correct 2 ms 70736 KB Output is correct
3 Correct 2 ms 70736 KB Output is correct
4 Correct 3 ms 70736 KB Output is correct
5 Correct 3 ms 70736 KB Output is correct
6 Correct 2 ms 70736 KB Output is correct
7 Correct 2 ms 70736 KB Output is correct
8 Correct 2 ms 70736 KB Output is correct
9 Correct 3 ms 70736 KB Output is correct
10 Correct 3 ms 70736 KB Output is correct
11 Correct 2 ms 70736 KB Output is correct
12 Correct 2 ms 70736 KB Output is correct
13 Correct 2 ms 70736 KB Output is correct
14 Correct 2 ms 70736 KB Output is correct
15 Correct 2 ms 70736 KB Output is correct
16 Correct 2 ms 70736 KB Output is correct
17 Correct 2 ms 70736 KB Output is correct
18 Correct 2 ms 70736 KB Output is correct
19 Correct 2 ms 70736 KB Output is correct
20 Correct 2 ms 70736 KB Output is correct
21 Correct 2 ms 70736 KB Output is correct
22 Correct 2 ms 70736 KB Output is correct
23 Incorrect 4 ms 70736 KB Output isn't correct
24 Halted 0 ms 0 KB -