oj.uz

Submission #893703

# Submission time Handle Problem Language Result Execution time Memory
893703 2023-12-27T10:01:52 Z yellowtoad Horses (IOI15_horses) C++17
17 / 100
 1033 ms 43576 KB 
#include "horses.h"
#include <iostream>
using namespace std;

const long long mod = 1e9+7;
long long n, a[500010], b[500010], node[2000010][3];
bool done;

/*
0: x product
1: max x
2: max y
*/

void build(int id, int x, int y) {
	if (x == y) {
		node[id][0] = a[x]%mod;
		node[id][1] = a[x];
		node[id][2] = b[x];
		return;
	}
	int mid = (x+y)/2;
	build(id*2,x,mid);
	build(id*2+1,mid+1,y);
	node[id][0] = (node[id*2][0]*node[id*2+1][0])%mod;
	node[id][1] = max(node[id*2][1],node[id*2+1][1]);
	node[id][2] = max(node[id*2][2],node[id*2+1][2]);
}

void update(int id, int jd, int x, int y, int pos, int val) {
	if (x == y) {
		node[id][jd] = val;
		return;
	}
	int mid = (x+y)/2;
	if (pos <= mid) update(id*2,jd,x,mid,pos,val);
	else update(id*2+1,jd,mid+1,y,pos,val);
	if (jd == 0) node[id][0] = (node[id*2][0]*node[id*2+1][0])%mod;
	else if (jd == 1) node[id][1] = max(node[id*2][1],node[id*2+1][1]);
	else node[id][2] = max(node[id*2][2],node[id*2+1][2]);
}

int nxt(int id, int x, int y, int r) {
	if (x > r) return 0;
	if (node[id][1] == 1) return 0;
	if (x == y) {
		done = 1;
		return x;
	}
	int mid = (x+y)/2, tmp = nxt(id*2+1,mid+1,y,r);
	if (!done) return nxt(id*2,x,mid,r);
	else return tmp;
}

int find_max(int id, int x, int y, int l, int r) {
	if ((l <= x) && (y <= r)) return node[id][2];
	if ((y < l) || (r < x)) return 0;
	int mid = (x+y)/2;
	return max(find_max(id*2,x,mid,l,r),find_max(id*2+1,mid+1,y,l,r));
}

int find_pro(int id, int x, int y, int l, int r) {
	if ((l <= x) && (y <= r)) return node[id][0];
	if ((y < l) || (r < x)) return 1;
	int mid = (x+y)/2;
	return (find_pro(id*2,x,mid,l,r)*find_pro(id*2+1,mid+1,y,l,r))%mod;
}

int solve() {
	int cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
	while (maxx <= 1e9+7) {
		maxx = max(maxx,find_max(1,1,n,cur+1,lst));
		lst = cur+1;
		maxx *= find_pro(1,1,n,lst,lst);
		done = 0;
		if (cur == -1) break;
		cur = nxt(1,1,n,cur)-1;
	}
	return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) a[i+1] = X[i], b[i+1] = Y[i];
	build(1,1,n);
	return solve();
}

int updateX(int pos, int val) {
	pos++;
	update(1,0,1,n,pos,val%mod);
	update(1,1,1,n,pos,val);
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	update(1,2,1,n,pos,val);
	return solve();
}

Compilation message

horses.cpp: In function 'int find_max(int, int, int, int, int)':
horses.cpp:56:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |  if ((l <= x) && (y <= r)) return node[id][2];
      |                                   ~~~~~~~~~~^
horses.cpp: In function 'int find_pro(int, int, int, int, int)':
horses.cpp:63:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |  if ((l <= x) && (y <= r)) return node[id][0];
      |                                   ~~~~~~~~~~^
horses.cpp: In function 'int solve()':
horses.cpp:70:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  int cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
      |                    ^
horses.cpp:70:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  int cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
      |                      ^
horses.cpp:70:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  int cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
      |                                  ^
horses.cpp:72:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   maxx = max(maxx,find_max(1,1,n,cur+1,lst));
      |                                ^
horses.cpp:74:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |   maxx *= find_pro(1,1,n,lst,lst);
      |                        ^
horses.cpp:77:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |   cur = nxt(1,1,n,cur)-1;
      |                 ^
horses.cpp:79:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod;
      |                                  ^
horses.cpp:79:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |  build(1,1,n);
      |            ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:91:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  update(1,0,1,n,pos,val%mod);
      |               ^
horses.cpp:92:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |  update(1,1,1,n,pos,val);
      |               ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  update(1,2,1,n,pos,val);
      |               ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4532 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4540 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4540 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4540 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 1 ms 4544 KB Output is correct
21 Incorrect 1 ms 4444 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4540 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4540 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Halted 0 ms 0 KB -