oj.uz

Submission #834246

# Submission time Handle Problem Language Result Execution time Memory
834246 2023-08-22T12:12:34 Z TB_ Horses (IOI15_horses) C++17
54 / 100
 700 ms 106472 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;
	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;
	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:46:22: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long double>, long double>::value_type' {aka 'long double'} to 'double' may change value [-Wfloat-conversion]
   46 |    valLog = prefLog[l];
      |                      ^
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 member function 'void Node::update(int, int, long long int, long long int)':
horses.cpp:62:42: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   62 |    addLog += log10l(upVal)-log10l(downVal);
      |                                          ^
horses.cpp:67:42: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   67 |    valLog += log10l(upVal)-log10l(downVal);
      |                                          ^
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:118:28: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
  118 |   currentLog += log10l(x[i]);
      |                            ^
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 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 300 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 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 0 ms 300 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 224 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 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 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 212 KB Output is correct
23 Correct 3 ms 440 KB Output is correct
24 Correct 2 ms 528 KB Output is correct
25 Correct 3 ms 440 KB Output is correct
26 Correct 3 ms 436 KB Output is correct
27 Correct 2 ms 440 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 4 ms 528 KB Output is correct
31 Correct 2 ms 440 KB Output is correct
32 Correct 2 ms 436 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 103956 KB Output is correct
2 Correct 631 ms 106392 KB Output is correct
3 Correct 612 ms 106384 KB Output is correct
4 Correct 700 ms 106368 KB Output is correct

Subtask #4
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 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 300 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 1 ms 212 KB Output is correct
16 Correct 0 ms 300 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 304 KB Output is correct
20 Correct 0 ms 300 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 3 ms 444 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 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 153 ms 106124 KB Output is correct
34 Correct 149 ms 105500 KB Output is correct
35 Correct 144 ms 105496 KB Output is correct
36 Correct 154 ms 105488 KB Output is correct
37 Correct 141 ms 104208 KB Output is correct
38 Correct 144 ms 105152 KB Output is correct
39 Correct 137 ms 104116 KB Output is correct
40 Correct 190 ms 105384 KB Output is correct
41 Correct 130 ms 104188 KB Output is correct
42 Correct 128 ms 104228 KB Output is correct
43 Correct 123 ms 105404 KB Output is correct
44 Incorrect 152 ms 105368 KB Output isn't correct
45 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 304 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 1 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 300 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 304 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 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 2 ms 460 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 468 KB Output is correct
30 Correct 4 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 271 ms 106360 KB Output is correct
34 Correct 630 ms 106292 KB Output is correct
35 Correct 595 ms 106284 KB Output is correct
36 Correct 694 ms 106472 KB Output is correct
37 Correct 149 ms 105592 KB Output is correct
38 Correct 155 ms 105588 KB Output is correct
39 Correct 145 ms 105452 KB Output is correct
40 Correct 159 ms 105436 KB Output is correct
41 Correct 144 ms 104208 KB Output is correct
42 Correct 135 ms 105148 KB Output is correct
43 Correct 136 ms 104100 KB Output is correct
44 Correct 195 ms 105604 KB Output is correct
45 Correct 129 ms 104116 KB Output is correct
46 Correct 128 ms 104256 KB Output is correct
47 Correct 124 ms 105284 KB Output is correct
48 Incorrect 130 ms 105592 KB Output isn't correct
49 Halted 0 ms 0 KB -