oj.uz

Submission #717218

# Submission time Handle Problem Language Result Execution time Memory
717218 2023-04-01T14:49:01 Z dsyz Horses (IOI15_horses) C++17
17 / 100
 1334 ms 193844 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using ld = long double;
#define MAXN (500005)
ll N;
ll mod = 1e9 + 7;
int x[MAXN], y[MAXN];
struct node{
	ll s,e,m;
	ld lazyadd;
	pair<ld,ll> v;
	node *l,*r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = {0,s};
		lazyadd = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	pair<ld,ll> value(){
		if(s == e){
			v.first += lazyadd;
			lazyadd = 0;
			return v;
		}
		v.first += lazyadd;
		r -> lazyadd += lazyadd;
		l -> lazyadd += lazyadd;
		lazyadd = 0;
		return v;
	}
	void update(ll x,ll y,ld val){
		if(s == x && e == y) lazyadd += val;
		else{
			if(x > m) r -> update(x,y,val);
			else if(y <= m) l -> update(x,y,val);
			else l -> update(x,m,val), r -> update(m + 1,y,val);
			v = max(l->value(),r->value());
		}
	}
	pair<ld,ll> rmq(ll x,ll y){
		value();
		if(s == x && e == y) return value();
		else if(x > m) return r -> rmq(x,y);
		else if(y <= m) return l -> rmq(x,y);
		else return max(l -> rmq(x,m),r -> rmq(m + 1,y)); 
	}
} *root1;
struct node2{
	ll s, e, m, val, lazy;
	node2 *l, *r;
	node2(ll S, ll E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node2(s,m);
			r = new node2(m + 1,e);
		}
	}
	void propogate(){
		if(lazy==0) return;
		val += lazy*(e-s+1);
		val %= mod;
		if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
			l->lazy += lazy;
			l->lazy %= mod;
			r->lazy += lazy;
			r->lazy %= mod;
		}
		lazy = 0;
	}
	void update(int S, int E, ll V){
		if(s == S && e == E) lazy += V, lazy %= mod;
		else{
			if(E <= m) l->update(S, E, V);
			else if (m < S) r->update(S, E, V);
			else l->update(S, m, V),r->update(m+1, E, V);
			l->propogate(),r->propogate();
			val = (l->val + r->val) % mod;
		}
	}
	ll query(int S, int E){
		propogate(); //remember to propogate
		if(s == S && e == E) return val; 
		else if(E <= m) return l->query(S, E); 
		else if(S >= m+1) return r->query(S, E);
		else return (l->query(S, m) + r->query(m+1, E)) % mod; 
	}
} *root2;
int init(int n, int X[], int Y[]) {
	N = n;
	for(ll i = 0;i < N;i++){
		x[i] = X[i];
		y[i] = Y[i];
	}
	root1 = new node(0,N + 5);
	root2 = new node2(0,N + 5);
	ld logXprefix = 0;
	for(ll i = 0;i < N;i++){
		logXprefix += log(x[i]);
		root1 -> update(i,i,logXprefix + log(y[i]));
	}
	ll prefixX = 1;
	for(ll i = 0;i < N;i++){
		prefixX *= x[i];
		prefixX %= mod;
		root2 -> update(i,i,prefixX);
	}
	pair<ld,ll> best = root1 -> rmq(0,N - 1);
	ll index = best.second;
	return (root2 -> query(index,index) * y[index]) % mod;
}

int updateX(int pos, int val) { //pos is 0-indexed
	root1 -> update(pos,N - 1,-1 * log(x[pos]));
	ll front = root2 -> query(pos,pos);
	root2 -> update(pos,N - 1,-1 * front + mod);
	ll oldx = x[pos];
	x[pos] = val;
	root1 -> update(pos,N - 1,log(x[pos]));
	ll add = (((front - oldx) % mod) + mod) % mod;
	root2 -> update(pos,N - 1,add);
	pair<ld,ll> best = root1 -> rmq(0,N - 1);
	ll index = best.second;
	return (root2 -> query(index,index) * y[index]) % mod;
}

int updateY(int pos, int val) {
	root1 -> update(pos,pos,-1 * log(y[pos]));
	y[pos] = val;
	root1 -> update(pos,pos,log(y[pos]));
	pair<ld,ll> best = root1 -> rmq(0,N - 1);
	ll index = best.second;
	return (root2 -> query(index,index) * y[index]) % mod;
}

Compilation message

horses.cpp: In member function 'void node::update(ll, ll, ld)':
horses.cpp:38:22: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   38 |  void update(ll x,ll y,ld val){
      |                   ~~~^
horses.cpp:9:14: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |              ^
horses.cpp:38:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   38 |  void update(ll x,ll y,ld val){
      |              ~~~^
horses.cpp:9:5: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In member function 'std::pair<long double, long long int> node::rmq(ll, ll)':
horses.cpp:47:26: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   47 |  pair<ld,ll> rmq(ll x,ll y){
      |                       ~~~^
horses.cpp:9:14: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |              ^
horses.cpp:47:21: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   47 |  pair<ld,ll> rmq(ll x,ll y){
      |                  ~~~^
horses.cpp:9:5: note: shadowed declaration is here
    9 | int x[MAXN], y[MAXN];
      |     ^
horses.cpp: In member function 'void node2::update(int, int, ll)':
horses.cpp:84:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |    else l->update(S, m, V),r->update(m+1, E, V);
      |                      ^
horses.cpp:84:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |    else l->update(S, m, V),r->update(m+1, E, V);
      |                                      ~^~
horses.cpp: In member function 'll node2::query(int, int)':
horses.cpp:94:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |   else return (l->query(S, m) + r->query(m+1, E)) % mod;
      |                            ^
horses.cpp:94:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |   else return (l->query(S, m) + r->query(m+1, E)) % mod;
      |                                          ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:114:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   root2 -> update(i,i,prefixX);
      |                   ^
horses.cpp:114:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   root2 -> update(i,i,prefixX);
      |                     ^
horses.cpp:118:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:118:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:118:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:124:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  root2 -> update(pos,N - 1,-1 * front + mod);
      |                      ~~^~~
horses.cpp:129:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  root2 -> update(pos,N - 1,add);
      |                      ~~^~~
horses.cpp:132:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:132:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:132:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:141:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                         ^~~~~
horses.cpp:141:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |                               ^~~~~
horses.cpp:141:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |  return (root2 -> query(index,index) * y[index]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 0 ms 212 KB Output is correct
10 Correct 1 ms 316 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 284 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 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 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 308 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 0 ms 316 KB Output is correct
14 Correct 1 ms 316 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 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 228 KB Output is correct
21 Incorrect 0 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 Correct 946 ms 185232 KB Output is correct
2 Incorrect 1334 ms 193844 KB Output isn't correct
3 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 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 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 260 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 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 308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 312 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 Incorrect 1 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 1 ms 340 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 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 312 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 316 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -