oj.uz

Submission #54710

# Submission time Handle Problem Language Result Execution time Memory
54710 2018-07-04T17:47:56 Z aome Horses (IOI15_horses) C++17
17 / 100
 136 ms 42060 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];
double val[N];

int binPow(int x, int y) {
	if (!y) return 1;
	int ret = binPow(x, y >> 1);
	ret = 1LL * ret * ret % mod;
	if (y & 1) ret = 1LL * ret * x % mod;
	return ret;
}

struct SegmentTree {
	struct Node {
		int pos, prd;
		double val, lazy; 

		void debug() {
			cout << "#node " << pos << ' ' << prd << ' ' << val << ' ' << lazy << '\n'; 
		}
	};

	Node T[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;
		}
		z.prd = 1LL * x.prd * y.prd % mod;
		return z;
	}

	void build(int i, int l, int r) {
		if (l == r) {
			T[i].pos = l, T[i].prd = x[l];
			T[i].val = val[l], T[i].lazy = 0;
			return;
		}
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = merge(T[i << 1], T[i << 1 | 1]);
		// cout << l << ' ' << r << '\n';
		// T[i].debug();
	}

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

	void updX(int i, int l, int r, int L, int R, double v) {
		push(i, l, r);
		if (L > r || l > R) return;
		if (L <= l && r <= R) {
			T[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);
		T[i] = merge(T[i << 1], T[i << 1 | 1]);
	}

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

	void updPrd(int i, int l, int r, int p, int v) {
		push(i, l, r);
		if (l == r) {
			T[i].prd = 1LL * T[i].prd * binPow(x[p], mod - 2) % mod;
			x[p] = v;
			T[i].prd = 1LL * T[i].prd * x[p] % mod;
			return; 
		}
		if (mid >= p) updPrd(i << 1, l, mid, p, v);
		else updPrd(i << 1 | 1, mid + 1, r, p, v);
		T[i] = merge(T[i << 1], T[i << 1 | 1]);
	}

	int getPrd(int i, int l, int r, int L, int R) {
		push(i, l, r);
		if (l > R || L > r) return 1;
		if (L <= l && r <= R) return T[i].prd;
		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.T[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.T[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.T[1].pos;
	return 1LL * IT.getPrd(1, 0, n - 1, 0, opt) * y[opt] % mod;
}

Compilation message

horses.cpp: In function 'int binPow(int, int)':
horses.cpp:14:24: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 int binPow(int x, int y) {
                        ^
horses.cpp:11:11: note: shadowed declaration is here
 int x[N], y[N];
           ^
horses.cpp:14:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int binPow(int x, int y) {
                        ^
horses.cpp:11:5: note: shadowed declaration is here
 int x[N], y[N];
     ^
horses.cpp:17:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ret = 1LL * ret * ret % mod;
        ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:18:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if (y & 1) ret = 1LL * ret * x % mod;
                   ~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'SegmentTree::Node SegmentTree::merge(SegmentTree::Node&, SegmentTree::Node&)':
horses.cpp:36: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:36: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:44:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   z.prd = 1LL * x.prd * y.prd % mod;
           ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void SegmentTree::updY(int, int, int, int, double)':
horses.cpp:84:34: warning: conversion to 'int' from 'double' may alter its value [-Wfloat-conversion]
    T[i].val -= log(y[p]), y[p] = v, T[i].val += log(y[p]);
                                  ^
horses.cpp: In member function 'void SegmentTree::updPrd(int, int, int, int, int)':
horses.cpp:95:54: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    T[i].prd = 1LL * T[i].prd * binPow(x[p], mod - 2) % mod;
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:97:37: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    T[i].prd = 1LL * T[i].prd * x[p] % mod;
               ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int SegmentTree::getPrd(int, int, int, int, int)':
horses.cpp:109: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:130: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:133:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateX(int pos, int val) {
                             ^
horses.cpp:12:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:137: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:140:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
 int updateY(int pos, int val) {
                             ^
horses.cpp:12:8: note: shadowed declaration is here
 double val[N];
        ^~~
horses.cpp:143: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 436 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 708 KB Output is correct
8 Correct 2 ms 708 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 3 ms 708 KB Output is correct
11 Correct 2 ms 708 KB Output is correct
12 Correct 3 ms 804 KB Output is correct
13 Correct 2 ms 804 KB Output is correct
14 Correct 2 ms 804 KB Output is correct
15 Correct 2 ms 848 KB Output is correct
16 Correct 2 ms 848 KB Output is correct
17 Correct 2 ms 848 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 2 ms 848 KB Output is correct
20 Correct 3 ms 848 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 42060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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