oj.uz

Submission #667409

# Submission time Handle Problem Language Result Execution time Memory
667409 2022-12-01T09:36:07 Z penguin133 Horses (IOI15_horses) C++14
17 / 100
 631 ms 161756 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<ll, ll>
#define fi first
#define se second
ll x[500005], y[500005], n;
const ll mod = 1e9 + 7;
struct node{
	ll s,e,m,val,lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0, lazy = 1;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			val = max(l->val, r->val);
		}
		else val = x[s];
	}
	void propo(){
		if(lazy != 1){
			val *= lazy;
			val %= mod;
			if(s != e)l->lazy *= lazy, r->lazy *= lazy, l->lazy %= mod, r->lazy %= mod;
			lazy = 1;
		}
	}
	void upd(int a, int b, int c){
		if(s == a && e == b)lazy *= c, lazy %= mod;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b , c);
			l->propo(), r->propo();
			val = max(l->val, r->val);
		}
	}
	int query(int p){
		propo();
		if(s == e)return val;
		if(p <= m)return l->query(p);
		else return r->query(p);
	}
}*root;
ll expo(int a, int b, int c){
	if(b == 1)return a;
	if(b == 0)return 1;
	ll t = expo(a, b/2, c);
	t *= t, t %= c;
	if(b%2)t *= a, t %= c;
	return t;
}
struct node2{
	ll s,e,m,val, pos;
	node2 *l, *r;
	node2(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		if(s != e){
			l = new node2(s, m);
			r = new node2(m+1, e);
			if(l->val >= r->val)pos = l->pos;
			else pos = r->pos;
			val = max(l->val, r->val);
		}
		else val = y[s], pos = s;
	}
	void upd(int p, int v){
		if(s == e)val = v;
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = max(l->val, r->val);
			if(l->val >= r->val)pos = l->pos;
			else pos = r->pos;
		}
	}
	pi query(int a, int b){
		if(a == s && b == e)return {val, pos};
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return max(l->query(a, m), r->query(m+1, b));
	}
}*root2;
 
set<int>s;
set<int> :: reverse_iterator it;
 
int answer(){
	if(s.empty())return root2->query(1, n).fi;
	it = s.rbegin();
	ll cur = 0, prev = n, in = n;
	while(cur <= 1e9 && it != s.rend()){
		pi tmp = root2->query(*it, prev);
		if(tmp.fi > cur)cur = tmp.fi, in = tmp.se;
		cur *= x[*it];
		prev = *it - 1;
		
		it++;
	}
  if(prev == 0)prev++;
	return max(root->query(in) * y[in], root2->query(1, prev).fi) % mod;
}
 
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0;i<n;i++)x[i+1] = X[i], y[i+1] = Y[i];
	root = new node(1, n);
	for(int i=1;i<n;i++)root->upd(i+1, n, x[i]); 
	root2 = new node2(1, n);
	for(int i=1;i<=n;i++)if(x[i] > 1)s.insert(i);
	return answer();
}
 
int updateX(int pos, int val) {
	pos++;
	int tmp = x[pos];
	if(tmp > 1)s.erase(pos);
	if(val > 1)s.insert(pos);
	x[pos] = val;
	root->upd(pos, n, val);
	root->upd(pos, n, expo(tmp, mod-2, mod));
	
	return answer();
}
 
int updateY(int pos, int val) {
	pos++;
	root2->upd(pos, val);
  y[pos] = val;
	return answer();
}

Compilation message

horses.cpp: In constructor 'node::node(int, int)':
horses.cpp:17:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   17 |    l = new node(s, m);
      |                 ^
horses.cpp:17:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   17 |    l = new node(s, m);
      |                    ^
horses.cpp:18:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   18 |    r = new node(m+1, e);
      |                 ~^~
horses.cpp:18:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   18 |    r = new node(m+1, e);
      |                      ^
horses.cpp: In member function 'void node::upd(int, int, int)':
horses.cpp:36:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   36 |    else l->upd(a, m, c), r->upd(m+1, b , c);
      |                   ^
horses.cpp:36:34: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   36 |    else l->upd(a, m, c), r->upd(m+1, b , c);
      |                                 ~^~
horses.cpp: In member function 'int node::query(int)':
horses.cpp:43:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   43 |   if(s == e)return val;
      |                    ^~~
horses.cpp: In constructor 'node2::node2(int, int)':
horses.cpp:63:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |    l = new node2(s, m);
      |                  ^
horses.cpp:63:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   63 |    l = new node2(s, m);
      |                     ^
horses.cpp:64:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |    r = new node2(m+1, e);
      |                  ~^~
horses.cpp:64:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |    r = new node2(m+1, e);
      |                       ^
horses.cpp: In member function 'std::pair<long long int, long long int> node2::query(int, int)':
horses.cpp:85:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |   else return max(l->query(a, m), r->query(m+1, b));
      |                               ^
horses.cpp:85:45: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |   else return max(l->query(a, m), r->query(m+1, b));
      |                                            ~^~
horses.cpp: In function 'int answer()':
horses.cpp:93:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |  if(s.empty())return root2->query(1, n).fi;
      |                                      ^
horses.cpp:6:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    6 | #define fi first
      |            ^
horses.cpp:93:41: note: in expansion of macro 'fi'
   93 |  if(s.empty())return root2->query(1, n).fi;
      |                                         ^~
horses.cpp:96:8: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   96 |  while(cur <= 1e9 && it != s.rend()){
      |        ^~~
horses.cpp:97:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |   pi tmp = root2->query(*it, prev);
      |                              ^~~~
horses.cpp:105:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |  return max(root->query(in) * y[in], root2->query(1, prev).fi) % mod;
      |                         ^~
horses.cpp:105:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |  return max(root->query(in) * y[in], root2->query(1, prev).fi) % mod;
      |                                                      ^~~~
horses.cpp:105:64: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  105 |  return max(root->query(in) * y[in], root2->query(1, prev).fi) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  111 |  root = new node(1, n);
      |                     ^
horses.cpp:112:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  for(int i=1;i<n;i++)root->upd(i+1, n, x[i]);
      |                                     ^
horses.cpp:112:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  for(int i=1;i<n;i++)root->upd(i+1, n, x[i]);
      |                                        ~~~^
horses.cpp:113:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |  root2 = new node2(1, n);
      |                       ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |  int tmp = x[pos];
      |            ~~~~~^
horses.cpp:124:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  root->upd(pos, n, val);
      |                 ^
horses.cpp:125:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |  root->upd(pos, n, expo(tmp, mod-2, mod));
      |                 ^
horses.cpp:125:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |  root->upd(pos, n, expo(tmp, mod-2, mod));
      |                    ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.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 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 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 284 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 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 1 ms 212 KB Output is correct
7 Correct 0 ms 308 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 0 ms 212 KB Output is correct
18 Correct 1 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 Incorrect 0 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 161756 KB Output is correct
2 Correct 631 ms 161748 KB Output is correct
3 Incorrect 624 ms 161728 KB Output isn't correct
4 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 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 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 1 ms 212 KB Output is correct
22 Incorrect 0 ms 212 KB Output isn't correct
23 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 0 ms 212 KB Output is correct
5 Correct 1 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 216 KB Output is correct
9 Correct 1 ms 216 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 224 KB Output is correct
13 Correct 1 ms 224 KB Output is correct
14 Correct 1 ms 220 KB Output is correct
15 Correct 1 ms 224 KB Output is correct
16 Correct 0 ms 224 KB Output is correct
17 Correct 0 ms 220 KB Output is correct
18 Correct 0 ms 224 KB Output is correct
19 Correct 1 ms 220 KB Output is correct
20 Correct 0 ms 220 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 0 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -