oj.uz

Submission #834066

# Submission time Handle Problem Language Result Execution time Memory
834066 2023-08-22T10:30:08 Z TB_ Horses (IOI15_horses) C++17
17 / 100
 483 ms 98776 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;
 
 
vl x, y;
vector<long double> prefLog;
 
struct Node{
	Node *lnode, *rnode;
	int l, r;
	long double valLog = 0, addLog = 0;
 
	Node(int l, int r) : l(l), r(r){
		if(r-l == 1) {
			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, long double upVal){
		if(r <= lo || hi <= l) return;
		if(r <= hi && lo <= l){
			addLog += upVal;
			valLog += upVal;
			return;
		}
		push();
		lnode->update(lo, hi, upVal);
		rnode->update(lo, hi, upVal);
		valLog = max(lnode->valLog, rnode->valLog);
	}
 
	long double query(){
		if(r-l == 1) return valLog;
		push();
		if(lnode->valLog >rnode->valLog) return lnode->query();
		else return rnode->query();
	}
 
	void push(){
		lnode->addLog += addLog;
		lnode->valLog += addLog;
		rnode->addLog += addLog;
		rnode->valLog += addLog;
		addLog = 0;
	}
};
 
Node *st;
vector<long double> logVals = {log10l(INF)};
 
long double binPow(long double currentVal){
	long double lo = 0;
	long double hi = INF+10;
	fo(i, 50){
		long double mid = (lo+hi) / 2;
		if(log10l(mid)>=currentVal) hi = mid;
		else lo = mid;
	}
	return hi;
}
 
ll solve(long double currentVal){
	for(int i = 22; i >= 0; i--) if(currentVal >= logVals[i]) currentVal-=logVals[i];
	return round(binPow(currentVal));
}
 
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){
		currentLog += log10l(x[i]);
		prefLog.pb(currentLog+log10l(y[i]));
	}
	st = new Node(0, N);
	fo(i, 23) logVals.pb(logVals[i]*((long double)2));
	
	return solve(st->query());
}
 
long double customLog(ll lval){
	return (lval<0?-log10l(lval):log10l(lval));
}
 
int updateX(int pos, int val) {	
	long double delta = customLog(val)-customLog(x[pos]);
	x[pos] = val;
	st->update(pos, x.size(), delta);
	return solve(st->query());
}
 
int updateY(int pos, int val) {
	long double delta = customLog(val)-customLog(y[pos]);
	y[pos] = val;
	st->update(pos, pos+1, delta);
	return solve(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:22:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:19:9: note: shadowed declaration is here
   19 |  int l, r;
      |         ^
horses.cpp:22:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:19:6: note: shadowed declaration is here
   19 |  int l, r;
      |      ^
horses.cpp: In constructor 'Node::Node(int, int)':
horses.cpp:22:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:19:9: note: shadowed declaration is here
   19 |  int l, r;
      |         ^
horses.cpp:22:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:19:6: note: shadowed declaration is here
   19 |  int l, r;
      |      ^
horses.cpp: In constructor 'Node::Node(int, int)':
horses.cpp:22:18: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |              ~~~~^
horses.cpp:19:9: note: shadowed declaration is here
   19 |  int l, r;
      |         ^
horses.cpp:22:11: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   22 |  Node(int l, int r) : l(l), r(r){
      |       ~~~~^
horses.cpp:19:6: note: shadowed declaration is here
   19 |  int l, r;
      |      ^
horses.cpp: In function 'long long int solve(long double)':
horses.cpp:78:14: warning: conversion from 'long double' to 'long long int' may change value [-Wfloat-conversion]
   78 |  return round(binPow(currentVal));
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:88:16: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   88 |  int n = x.size();
      |          ~~~~~~^~
horses.cpp:96:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return solve(st->query());
      |         ~~~~~^~~~~~~~~~~~~
horses.cpp:86:5: warning: unused variable 'current' [-Wunused-variable]
   86 |  ll current = 1;
      |     ^~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:106:24: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  106 |  st->update(pos, x.size(), delta);
      |                  ~~~~~~^~
horses.cpp:107:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  return solve(st->query());
      |         ~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:114:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |  return solve(st->query());
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 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 0 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 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
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 1 ms 212 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 336 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 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

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 1 ms 260 KB Output is correct
4 Correct 0 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 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 1 ms 256 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
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 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 1 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 1 ms 236 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 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 240 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 1 ms 300 KB Output isn't correct
22 Halted 0 ms 0 KB -