oj.uz

Submission #834143

# Submission time Handle Problem Language Result Execution time Memory
834143 2023-08-22T11:12:05 Z TB_ Horses (IOI15_horses) C++17
17 / 100
 192 ms 206708 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;
		if(r <= hi && lo <= l){
			mulVal = (mulVal * upVal)%(INF);
			downVal = (downVal * upVal)%(INF);
			addLog += log10l(upVal)-log10l(downVal);
			val = (val * upVal)%(INF);
			val = (val * modInverse(downVal))%(INF);
			valLog += log10l(upVal)-log10l(downVal);
			valLog = max(lnode->valLog, rnode->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) {	
	long double valPre = x[pos];
	x[pos] = val;
	st->update(pos, x.size(), val, valPre);
	return st->query();
}

int updateY(int pos, int val) {
	long double 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:60:42: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   60 |    addLog += log10l(upVal)-log10l(downVal);
      |                                          ^
horses.cpp:63:42: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   63 |    valLog += log10l(upVal)-log10l(downVal);
      |                                          ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:16: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  111 |  int n = x.size();
      |          ~~~~~~^~
horses.cpp:114:28: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
  114 |   currentLog += log10l(x[i]);
      |                            ^
horses.cpp:119:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |  return st->query();
      |         ~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:125:24: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  125 |  st->update(pos, x.size(), val, valPre);
      |                  ~~~~~~^~
horses.cpp:125:33: warning: conversion from 'long double' to 'long long int' may change value [-Wfloat-conversion]
  125 |  st->update(pos, x.size(), val, valPre);
      |                                 ^~~~~~
horses.cpp:126:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |  return st->query();
      |         ~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:132:30: warning: conversion from 'long double' to 'long long int' may change value [-Wfloat-conversion]
  132 |  st->update(pos, pos+1, val, valPre);
      |                              ^~~~~~
horses.cpp:133:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |  return st->query();
      |         ~~~~~~~~~^~

Subtask #1
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 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 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 1 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 1 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 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 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
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 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 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 1 ms 240 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 336 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 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 206708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
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 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 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 212 KB Output is correct
14 Correct 1 ms 336 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 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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 0 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 1 ms 336 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 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
21 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -