oj.uz

Submission #667415

# Submission time Handle Problem Language Result Execution time Memory
667415 2022-12-01T09:40:15 Z penguin133 Horses (IOI15_horses) C++14
100 / 100
 722 ms 174336 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(it == s.rend()){
        if(root2->query(1, prev + 1).fi > cur)in = root2->query(1, prev + 1).se;
		}
	}
	
	return (root->query(in) * y[in]) % 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:104:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |         if(root2->query(1, prev + 1).fi > cur)in = root2->query(1, prev + 1).se;
      |                            ~~~~~^~~
horses.cpp:104:73: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |         if(root2->query(1, prev + 1).fi > cur)in = root2->query(1, prev + 1).se;
      |                                                                    ~~~~~^~~
horses.cpp:108:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  108 |  return (root->query(in) * y[in]) % mod;
      |                      ^~
horses.cpp:108:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  108 |  return (root->query(in) * y[in]) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:114:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |  root = new node(1, n);
      |                     ^
horses.cpp:115:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |  for(int i=1;i<n;i++)root->upd(i+1, n, x[i]);
      |                                     ^
horses.cpp:115:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |  for(int i=1;i<n;i++)root->upd(i+1, n, x[i]);
      |                                        ~~~^
horses.cpp:116:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  root2 = new node2(1, n);
      |                       ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  int tmp = x[pos];
      |            ~~~~~^
horses.cpp:127:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |  root->upd(pos, n, val);
      |                 ^
horses.cpp:128:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  root->upd(pos, n, expo(tmp, mod-2, mod));
      |                 ^
horses.cpp:128:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  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 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 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 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
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 1 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 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 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 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 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 576 KB Output is correct
30 Correct 2 ms 580 KB Output is correct
31 Correct 2 ms 576 KB Output is correct
32 Correct 2 ms 596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 161700 KB Output is correct
2 Correct 628 ms 161668 KB Output is correct
3 Correct 626 ms 161700 KB Output is correct
4 Correct 721 ms 161796 KB Output is correct

Subtask #4
23.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 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 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 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 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 2 ms 572 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 2 ms 576 KB Output is correct
29 Correct 2 ms 576 KB Output is correct
30 Correct 3 ms 596 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 3 ms 592 KB Output is correct
33 Correct 224 ms 141312 KB Output is correct
34 Correct 212 ms 141368 KB Output is correct
35 Correct 457 ms 171692 KB Output is correct
36 Correct 373 ms 171588 KB Output is correct
37 Correct 250 ms 139608 KB Output is correct
38 Correct 273 ms 152312 KB Output is correct
39 Correct 179 ms 139392 KB Output is correct
40 Correct 381 ms 166752 KB Output is correct
41 Correct 179 ms 139320 KB Output is correct
42 Correct 214 ms 139596 KB Output is correct
43 Correct 348 ms 167152 KB Output is correct
44 Correct 370 ms 167108 KB Output is correct

Subtask #5
23.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 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 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 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 0 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 2 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 2 ms 576 KB Output is correct
32 Correct 3 ms 576 KB Output is correct
33 Correct 489 ms 165572 KB Output is correct
34 Correct 623 ms 174336 KB Output is correct
35 Correct 620 ms 165492 KB Output is correct
36 Correct 722 ms 169304 KB Output is correct
37 Correct 215 ms 141372 KB Output is correct
38 Correct 192 ms 141348 KB Output is correct
39 Correct 372 ms 171744 KB Output is correct
40 Correct 380 ms 171600 KB Output is correct
41 Correct 217 ms 139644 KB Output is correct
42 Correct 280 ms 152296 KB Output is correct
43 Correct 183 ms 139340 KB Output is correct
44 Correct 374 ms 166760 KB Output is correct
45 Correct 180 ms 139340 KB Output is correct
46 Correct 197 ms 139572 KB Output is correct
47 Correct 337 ms 167036 KB Output is correct
48 Correct 353 ms 167116 KB Output is correct
49 Correct 414 ms 144384 KB Output is correct
50 Correct 375 ms 144464 KB Output is correct
51 Correct 449 ms 173524 KB Output is correct
52 Correct 445 ms 173188 KB Output is correct
53 Correct 516 ms 142712 KB Output is correct
54 Correct 388 ms 156236 KB Output is correct
55 Correct 302 ms 140380 KB Output is correct
56 Correct 517 ms 168548 KB Output is correct
57 Correct 309 ms 141136 KB Output is correct
58 Correct 389 ms 141576 KB Output is correct
59 Correct 342 ms 167076 KB Output is correct