oj.uz

Submission #396830

# Submission time Handle Problem Language Result Execution time Memory
396830 2021-04-30T19:27:53 Z Kenzo_1114 Horses (IOI15_horses) C++17
17 / 100
 507 ms 55364 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
const long long int MOD = 1e9 + 7;

int n;
long long int x[MAXN], y[MAXN];
long long int seg[2][4 * MAXN];
set<int> s;

void upd(bool f, int pos, int bg, int ed, int id, int val)
{
	if(bg == ed){	seg[f][pos] = (!f) ? val : id; return; }

	int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1;

	if(id <= mid)	upd(f, l, bg, mid, id, val);
	else 			upd(f, r, mid + 1, ed, id, val);

	if(!f)	seg[f][pos] = (seg[f][l] * seg[f][r]) % MOD;
	else	seg[f][pos] = (y[seg[f][l]] > y[seg[f][r]]) ? seg[f][l] : seg[f][r];
}

int qry(bool f, int pos, int bg, int ed, int p, int q)
{
	if(q < p || q < bg || ed < p)	return (!f) ? 1 : 0;
	if(p <= bg && ed <= q)			return seg[f][pos];

	int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1;

	if(!f)	return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD;

	l = qry(f, l, bg, mid, p, q);
	r = qry(f, r, mid + 1, ed, p, q);
	return (y[l] > y[r]) ? l : r;
}

int getAns()
{
	set<int> :: iterator l, r;
	int k = 0;

	l = s.end();
	while(k < 32 && l != s.begin())	k++, l--;

	r = l;	r++;
	int i = 0;
	long long int prefX = 1;
	while(r != s.end())
	{
//		printf("i = %d l = %d r = %d | ", i, *l, *r);
		int q = qry(1, 1, 1, n, *l + 1, *r - 1);
		if(prefX >= MOD || y[i] < prefX * y[q])
		{
			prefX = 1;
			i = q;
		}
		prefX *= x[*r];
//		printf("i = %d l = %d r = %d\n", i, *l, *r);

		if(prefX >= MOD || y[i] < prefX * y[*r])
		{
			prefX = 1;
			i = *r;
		}

		l++, r++;
	}

//	printf("i = %d\n", i);

	return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD;
}

int updateX(int id, int val)
{
	id++;
	if(val > 1)	s.insert(id);
	else		s.erase(id);
	x[id] = val;
	upd(0, 1, 1, n, id, val);

	return getAns();
}

int updateY(int id, int val)
{
	id++;
	y[id] = val;
	upd(1, 1, 1, n, id, val);

	return getAns();
}

int init(int N, int X[], int Y[])
{
	n = N;
	for(int i = n; i > 0; i--)	x[i] = X[i - 1];
	for(int i = n; i > 0; i--)	y[i] = Y[i - 1];

	for(int i = 1; i <= n; i++)	
	{
		upd(0, 1, 1, n, i, x[i]);
		upd(1, 1, 1, n, i, y[i]);
		if(x[i] > 1)	s.insert(i);
	}
	s.insert(0);
	s.insert(n + 1);

	return getAns();
}

Compilation message

horses.cpp: In function 'int qry(bool, int, int, int, int, int)':
horses.cpp:27:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |  if(p <= bg && ed <= q)   return seg[f][pos];
      |                                  ~~~~~~~~~~^
horses.cpp:31:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   31 |  if(!f) return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:72:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |  return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |   upd(0, 1, 1, n, i, x[i]);
      |                      ~~~^
horses.cpp:104:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |   upd(1, 1, 1, n, i, y[i]);
      |                      ~~~^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

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