oj.uz

Submission #834267

# Submission time Handle Problem Language Result Execution time Memory
834267 2023-08-22T12:26:50 Z TB_ Horses (IOI15_horses) C++17
100 / 100
 869 ms 127752 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, x) for(ll i = 0; i<x;i++)
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", "  << #y << " = " << y << endl;

typedef vector<ll> vl;

ll extEuclid(ll a, ll b, ll &x, ll &y) {    // pass x and y by ref 
    ll xx = y = 0; 
    ll yy = x = 1; 
    while (b) {                                    // repeats until b == 0 
        ll q = a/b; 
        tie(a, b) = tuple(b, a%b); 
        tie(x, xx) = tuple(xx, x-q*xx); 
        tie(y, yy) = tuple(yy, y-q*yy); 
    } 
    return a;                                      // returns gcd(a, b) 
} 
  
ll modInverse(ll b, ll m = INF) {                   // returns b^(-1) (mod m) 
    ll x, y; 
    ll d = extEuclid(b, m, x, y);                 // to get b*x + m*y == d 
    if (d != 1) return -1;                         // to indicate failure 
    // b*x + m*y == 1, now apply (mod m) to get b*x == 1 (mod m) 
    return (x+m)%m;                                // this is the answer 
} 


vl x, y, pref;
vector<long double> prefLog;

struct Node{
	Node *lnode, *rnode;
	int l, r;
	ll val = 1, mulVal = 1, devVal = 1;
	long double valLog = 0, addLog = 0;

	Node(int l, int r) : l(l), r(r){
		if(r-l == 1) {
			val = pref[l];
			valLog = prefLog[l];
		}else{
			int mid = (r+l)/2;
			lnode = new Node(l, mid);
			rnode = new Node(mid, r);
			valLog = max(lnode->valLog, rnode->valLog);
		}
	}

	void update(int lo, int hi, ll upVal, ll downVal){
		if(r <= lo || hi <= l) return;
		// deb2(l, r);
		// deb2(valLog, log10l(upVal)-log10l(downVal));
		if(r <= hi && lo <= l){
			mulVal = (mulVal * upVal)%(INF);
			devVal = (devVal * downVal)%(INF);
			addLog += log10l(upVal)-log10l(downVal);
			val = (val * upVal)%(INF);
			val = (val * modInverse(downVal))%(INF);
			// deb2(valLog, log10l(upVal)-log10l(downVal));
			// deb2(valLog, valLog + log10l(upVal)-log10l(downVal));
			valLog += log10l(upVal)-log10l(downVal);
			// deb(valLog);
			return;
		}
		push();
		lnode->update(lo, hi, upVal, downVal);
		rnode->update(lo, hi, upVal, downVal);
		valLog = max(lnode->valLog, rnode->valLog);
	}

	ll query(){
		if(r-l == 1) return val;
		push();
		ll res = 1;
		if(lnode->valLog >rnode->valLog) res = lnode->query();
		else res = rnode->query();
		valLog = max(lnode->valLog, rnode->valLog);
		return res;
	}

	void push(){
		lnode->mulVal = (lnode->mulVal * mulVal)%(INF);
		lnode->devVal = (lnode->devVal * devVal)%(INF);
		lnode->addLog += addLog;
		lnode->val = (lnode->val * mulVal)%(INF);
		lnode->val = (lnode->val * modInverse(devVal))%(INF);
		lnode->valLog += addLog;
		rnode->mulVal = (rnode->mulVal * mulVal)%(INF);
		rnode->devVal = (rnode->devVal * devVal)%(INF);
		rnode->addLog += addLog;
		rnode->val = (rnode->val * mulVal)%(INF);
		rnode->val = (rnode->val * modInverse(devVal))%(INF);
		rnode->valLog += addLog;
		addLog = 0;
		mulVal = 1;
		devVal = 1;
	}
};

Node *st;

int init(int N, int X[], int Y[]) {
	fo(i, N){
		x.pb(X[i]);
		y.pb(Y[i]);
	}
	ll current = 1;
	long double currentLog = 0;
	int n = x.size();
	fo(i, n){
		current = (current*x[i])%(INF);
		currentLog += log10l(x[i]);
		pref.pb((current*y[i])%(INF));
		prefLog.pb(currentLog+log10l(y[i]));
	}
	st = new Node(0, N);
	return st->query();
}

int updateX(int pos, int val) {	
	// deb("pre");
	ll valPre = x[pos];
	x[pos] = val;
	st->update(pos, x.size(), val, valPre);
	return st->query();
}

int updateY(int pos, int val) {
	ll valPre = y[pos];
	y[pos] = val;
	st->update(pos, pos+1, val, valPre);
	return st->query();
}


// static char _buffer[1024];
// static int _currentChar = 0;
// static int _charsNumber = 0;
// static FILE *_inputFile, *_outputFile;

// static inline int _read() {
//     if (_charsNumber < 0) {
//         exit(1);
//     }
//     if (!_charsNumber || _currentChar == _charsNumber) {
//         _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
//         _currentChar = 0;
//     }
//     if (_charsNumber <= 0) {
//         return -1;
//     }
//     return _buffer[_currentChar++];
// }

// static inline int _readInt() {
//     int c, x, s;
//     c = _read();
//     while (c <= 32) c = _read();
//     x = 0;
//     s = 1;
//     if (c == '-') {
//         s = -1;
//         c = _read();
//     }
//     while (c > 32) {
//         x *= 10;
//         x += c - '0';
//         c = _read();
//     }
//     if (s < 0) x = -x;
//     return x;
// }


// int main() {
// 	_inputFile = fopen("horses.in", "rb");
// 	_outputFile = fopen("horses.out", "w");
	
// 	int N; N = _readInt();

// 	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
// 	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

// 	for (int i = 0; i < N; i++) {
// 		X[i] = _readInt();
// 	}

// 	for (int i = 0; i < N; i++) {
// 		Y[i] = _readInt();
// 	}	

// 	fprintf(_outputFile,"%d\n",init(N,X,Y));

// 	int M; M = _readInt();

// 	for (int i = 0; i < M; i++) {
// 		int type; type = _readInt();
// 		int pos; pos = _readInt();
// 		int val; val = _readInt(); 

// 		if (type == 1) {
// 			fprintf(_outputFile,"%d\n",updateX(pos,val));
// 		} else if (type == 2) {
// 			fprintf(_outputFile,"%d\n",updateY(pos,val));
// 		}
// 	}

// 	return 0;
// }

Compilation message

horses.cpp: In constructor 'Node::Node(int, int)':
horses.cpp:43:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:39:9: note: shadowed declaration is here
   39 |  int l, r;
      |         ^
horses.cpp:43:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int l, r;
      |      ^
horses.cpp: In constructor 'Node::Node(int, int)':
horses.cpp:43:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:39:9: note: shadowed declaration is here
   39 |  int l, r;
      |         ^
horses.cpp:43:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int l, r;
      |      ^
horses.cpp: In constructor 'Node::Node(int, int)':
horses.cpp:43:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:39:9: note: shadowed declaration is here
   39 |  int l, r;
      |         ^
horses.cpp:43:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   43 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:39:6: note: shadowed declaration is here
   39 |  int l, r;
      |      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:115:16: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |  int n = x.size();
      |          ~~~~~~^~
horses.cpp:123:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  return st->query();
      |         ~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:24: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  130 |  st->update(pos, x.size(), val, valPre);
      |                  ~~~~~~^~
horses.cpp:131:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |  return st->query();
      |         ~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return st->query();
      |         ~~~~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 3 ms 572 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 2 ms 552 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 118840 KB Output is correct
2 Correct 692 ms 119348 KB Output is correct
3 Correct 650 ms 119316 KB Output is correct
4 Correct 747 ms 119364 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 3 ms 568 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 3 ms 440 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 2 ms 436 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 167 ms 118408 KB Output is correct
34 Correct 176 ms 118484 KB Output is correct
35 Correct 153 ms 118484 KB Output is correct
36 Correct 166 ms 118380 KB Output is correct
37 Correct 164 ms 118212 KB Output is correct
38 Correct 157 ms 118184 KB Output is correct
39 Correct 156 ms 118128 KB Output is correct
40 Correct 208 ms 118456 KB Output is correct
41 Correct 146 ms 118224 KB Output is correct
42 Correct 148 ms 118100 KB Output is correct
43 Correct 137 ms 118372 KB Output is correct
44 Correct 139 ms 118280 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 272 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 300 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 3 ms 560 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 2 ms 436 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 335 ms 119324 KB Output is correct
34 Correct 690 ms 119240 KB Output is correct
35 Correct 654 ms 119292 KB Output is correct
36 Correct 753 ms 119372 KB Output is correct
37 Correct 176 ms 118432 KB Output is correct
38 Correct 172 ms 118452 KB Output is correct
39 Correct 153 ms 118472 KB Output is correct
40 Correct 165 ms 118464 KB Output is correct
41 Correct 163 ms 118188 KB Output is correct
42 Correct 154 ms 118116 KB Output is correct
43 Correct 155 ms 118076 KB Output is correct
44 Correct 204 ms 118396 KB Output is correct
45 Correct 168 ms 118144 KB Output is correct
46 Correct 147 ms 118180 KB Output is correct
47 Correct 136 ms 118352 KB Output is correct
48 Correct 140 ms 118360 KB Output is correct
49 Correct 612 ms 123656 KB Output is correct
50 Correct 608 ms 123684 KB Output is correct
51 Correct 353 ms 127752 KB Output is correct
52 Correct 458 ms 127564 KB Output is correct
53 Correct 525 ms 122044 KB Output is correct
54 Correct 471 ms 122624 KB Output is correct
55 Correct 443 ms 120764 KB Output is correct
56 Correct 869 ms 125600 KB Output is correct
57 Correct 318 ms 121484 KB Output is correct
58 Correct 355 ms 122012 KB Output is correct
59 Correct 139 ms 124200 KB Output is correct