oj.uz

Submission #1005212

# Submission time Handle Problem Language Result Execution time Memory
1005212 2024-06-22T08:56:46 Z coolboy19521 Horses (IOI15_horses) C++17
17 / 100
 1500 ms 83544 KB 
#include"bits/stdc++.h"
#include"horses.h"
#define ld long double
#define i64 long long

using namespace std;

const int sz = 5e5 + 25;
const int md = 1e9 + 7;

i64 lz1m[sz * 4], lz1d[sz * 4];
i64 st1[sz * 4];
ld lz2m[sz * 4], lz2d[sz * 4];
pair<ld,int> st2[sz * 4];
ld d[sz];
int a[sz], b[sz], c[sz];
int n;

i64 bp(int x, int b) {
	if (0 == b) return 1;
	i64 r = bp(x, b / 2) % md;
	if (b % 2) return (r * r % md) * x % md;
	return r * r % md;
}

void build1(int le, int ri, int v) {
	lz1m[v] = 1;
	lz1d[v] = 1;
	if (le == ri) {
		st1[v] = c[le] * b[le] % md;
		return;
	}
	int mi = le + (ri - le) / 2;
	build1(le, mi, v * 2);
	build1(mi + 1, ri, v * 2 + 1);
}

void relax1(int v) {
	// cout << "PREV " << st1[v] << ' ' << lz1m[v] << ' ' << lz1d[v] << '\n';
	(st1[v] *= lz1m[v]) %= md;
	// cout << "AFTER MULT " << st1[v] << '\n';
	(st1[v] *= bp(lz1d[v], md - 2)) %= md;
	// cout << "NOW " << st1[v] << ' ' << bp(5, md - 2) << '\n';

	if (v * 2 < sz * 4) {
		lz1m[v * 2] *= lz1m[v];
		lz1m[v * 2 + 1] *= lz1m[v];
		lz1d[v * 2] *= lz1d[v];
		lz1d[v * 2 + 1] *= lz1d[v];
	}
	lz1m[v] = 1;
	lz1d[v] = 1;
}

void rupdate1(int le, int ri, int ql, int qr, int v, int m, int d) {
	relax1(v);
	if (le > qr || ri < ql) return;
	if (ql <= le && ri <= qr) {
		// cout << "RANGE UPDATE " << le << ' ' << ri << ' ' << m << ' ' << d << '\n';
		lz1m[v] *= m;
		lz1d[v] *= d;
		relax1(v);
		return;
	}
	int mi = le + (ri - le) / 2;
	rupdate1(le, mi, ql, qr, v * 2, m, d);
	rupdate1(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
}

void pupdate1(int le, int ri, int ix, int v, int m, int d) {
	relax1(v);
	if (le > ix || ri < ix) return;
	if (le == ix && ix == ri) {
		(st1[v] *= m) %= md;
		(st1[v] *= bp(d, md - 2)) %= md;
		return;
	}
	int mi = le + (ri - le) / 2;
	pupdate1(le, mi, ix, v * 2, m, d);
	pupdate1(mi + 1, ri, ix, v * 2 + 1, m, d);
}

int query1(int le, int ri, int ix, int v) {
	relax1(v);
	if (le > ix || ri < ix) return 0;
	if (le == ix && ix == ri) {
		return st1[v];
	}
	int mi = le + (ri - le) / 2;
	int lq = query1(le, mi, ix, v * 2);
	int rq = query1(mi + 1, ri, ix, v * 2 + 1);
	return lq + rq;
}

pair<ld,int> marj(int v) {
	auto le = st2[v * 2];
	auto ri = st2[v * 2 + 1];
	if (le.first > ri.first) {
		return le;
	}
	return ri;
}

void build2(int le, int ri, int v) {
	if (le == ri) {
		st2[v] = make_pair(d[le] + log10l(b[le]), le);
		return;
	}
	int mi = le + (ri - le) / 2;
	build2(le, mi, v * 2);
	build2(mi + 1, ri, v * 2 + 1);
	st2[v] = marj(v);
}

void relax2(int v) {
	st2[v].first += lz2m[v];
	st2[v].first -= lz2d[v];
	if (v * 2 < sz * 4) {
		lz2m[v * 2] += lz2m[v];
		lz2m[v * 2 + 1] += lz2m[v];
		lz2d[v * 2] += lz2d[v];
		lz2d[v * 2 + 1] += lz2d[v];
	}
	lz2m[v] = 0;
	lz2d[v] = 0;
}

void rupdate2(int le, int ri, int ql, int qr, int v, ld m, ld d) {
	relax2(v);
	if (le > qr || ri < ql) return;
	if (ql <= le && ri <= qr) {
		lz2m[v] += m;
		lz2d[v] += d;
		relax2(v);
		return;
	}
	int mi = le + (ri - le) / 2;
	rupdate2(le, mi, ql, qr, v * 2, m, d);
	rupdate2(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
	st2[v] = marj(v);
}

void pupdate2(int le, int ri, int ix, int v, ld m, ld d) {
	relax2(v);
	if (le > ix || ri < ix) return;
	if (le == ix && ri == ix) {
		st2[v].first += m;
		st2[v].first -= d;
		return;
	}
	int mi = le + (ri - le) / 2;
	pupdate2(le, mi, ix, v * 2, m, d);
	pupdate2(mi + 1, ri, ix, v * 2 + 1, m, d);
	st2[v] = marj(v);
}

int init(int N, int x[], int y[]) {
	n = N;
	c[0] = 1;

	for (int i = 1; i <= n; i ++) {
		a[i] = x[i - 1];
		b[i] = y[i - 1];
		c[i] = c[i - 1] * a[i] % md;
		d[i] = d[i - 1] + log10l(a[i]);
	}

	build1(1, n, 1);
	build2(1, n, 1);

	int ix = st2[1].second;
	// cout << "BEGIN " << ix << '\n';

	return query1(1, n, ix, 1);
}

int updateX(int pos, int val) {
	pos ++;
	rupdate1(1, n, pos, n, 1, val, a[pos]);
	rupdate2(1, n, pos, n, 1, log10l(val), log10l(a[pos]));
	a[pos] = val;
	relax2(1);
	int ix = st2[1].second;
	// cout << "QUERY X " << ix << ' ' << st2[1].first << '\n';

	return query1(1, n, ix, 1);
}

int updateY(int pos, int val) {
	pos ++;
	pupdate1(1, n, pos, 1, val, b[pos]);
	pupdate2(1, n, pos, 1, log10l(val), log10l(b[pos]));
	b[pos] = val;
	relax2(1);
	int ix = st2[1].second;

	return query1(1, n, ix, 1);
}

Compilation message

horses.cpp: In function 'long long int bp(int, int)':
horses.cpp:19:19: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   19 | i64 bp(int x, int b) {
      |               ~~~~^
horses.cpp:16:12: note: shadowed declaration is here
   16 | int a[sz], b[sz], c[sz];
      |            ^
horses.cpp: In function 'void relax1(int)':
horses.cpp:42:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  (st1[v] *= bp(lz1d[v], md - 2)) %= md;
      |                ~~~~~~^
horses.cpp: In function 'void rupdate1(int, int, int, int, int, int, int)':
horses.cpp:55:65: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   55 | void rupdate1(int le, int ri, int ql, int qr, int v, int m, int d) {
      |                                                             ~~~~^
horses.cpp:15:4: note: shadowed declaration is here
   15 | ld d[sz];
      |    ^
horses.cpp: In function 'void pupdate1(int, int, int, int, int, int)':
horses.cpp:70:57: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   70 | void pupdate1(int le, int ri, int ix, int v, int m, int d) {
      |                                                     ~~~~^
horses.cpp:15:4: note: shadowed declaration is here
   15 | ld d[sz];
      |    ^
horses.cpp: In function 'int query1(int, int, int, int)':
horses.cpp:87:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |   return st1[v];
      |          ~~~~~^
horses.cpp: In function 'void rupdate2(int, int, int, int, int, long double, long double)':
horses.cpp:128:63: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  128 | void rupdate2(int le, int ri, int ql, int qr, int v, ld m, ld d) {
      |                                                               ^
horses.cpp:15:4: note: shadowed declaration is here
   15 | ld d[sz];
      |    ^
horses.cpp: In function 'void pupdate2(int, int, int, int, long double, long double)':
horses.cpp:143:55: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  143 | void pupdate2(int le, int ri, int ix, int v, ld m, ld d) {
      |                                                       ^
horses.cpp:15:4: note: shadowed declaration is here
   15 | ld d[sz];
      |    ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 1 ms 12636 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 1 ms 12636 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 1 ms 12704 KB Output is correct
20 Correct 1 ms 12732 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 83544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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