oj.uz

Submission #1086978

# Submission time Handle Problem Language Result Execution time Memory
1086978 2024-09-12T01:27:15 Z the_coding_pooh Horses (IOI15_horses) C++14
0 / 100
 213 ms 41584 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define uwu return;

using namespace std;

const int SIZE = 5e5 + 5,  MOD = 1e9 + 7;

long long in_X[SIZE], in_Y[SIZE]; 

#define lc 2 * id
#define rc 2 * id + 1

struct ratio_query{
	long long rq_seg[4 * SIZE];
	
	void pull(int id){
		if(rq_seg[lc] == MOD || rq_seg[rc] == MOD) 
			rq_seg[id] = MOD;
		else{
			rq_seg[id] = rq_seg[lc] * rq_seg[rc];
			if(rq_seg[id] >= MOD) 
				rq_seg[id] = MOD;
		}
	}

	void build(int L, int R, int id){
		if(L == R){
			rq_seg[id] = in_X[L];
			return;
		}
		int M = (L + R) / 2;
		build(L, M, lc);
		build(M + 1, R, rc);
		pull(id);
		return;
	}

	void modify(int pos, int val, int L, int R, int id){
		if(L == R){
			in_X[pos] = val;
			rq_seg[id] = val;
			return;
		}

		int M = (L + R) / 2;
		if(pos <= M)
			modify(pos, val, L, M, lc);
		else
			modify(pos, val, M + 1, R, rc);
		pull(id);
		return;
	}

	long long query(int ql, int qr, int L, int R, int id){
		if(ql <= L && R <= qr){
			return rq_seg[id];
		}
		int M = (L + R) / 2;
		long long retl = 1, retr = 1;
		if(ql <= M) 
			retl = query(ql, min(M, qr), L, M, lc);
		if(qr > M)
			retr = query(max(ql, M + 1), qr, M + 1, R, rc);
		if(retl == MOD || retr == MOD) 
			return MOD;
		return (retl * retr >= MOD ? MOD : retl * retr);
	}
}rq;

struct node{
	long long pi_X, mx_tm, mx_pos;
}SEGTree[SIZE];

#define nd SEGTree[id]
#define ln SEGTree[lc]
#define rn SEGTree[rc]

void pull(int id){
	long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
	if(tms == MOD || tms * in_Y[rn.mx_pos] >= in_Y[ln.mx_pos]){
		nd.mx_tm = (ln.pi_X * rn.mx_tm) % MOD;
		nd.mx_pos = rn.mx_pos;
	}
	else{
		nd.mx_tm = ln.mx_tm;
		nd.mx_pos = ln.mx_pos;
	}
	nd.pi_X = (ln.pi_X * rn.pi_X) % MOD;
	return;
}


void build(int L, int R, int id){
	if(L == R){
		SEGTree[id].pi_X = in_X[L];
		SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		SEGTree[id].mx_pos = L;
		return;
	}
	int M = (L + R) / 2;
	build(L, M, lc);
	build(M + 1, R, rc);
	pull(id);
	return;
}

void modify(int pos, int val, bool is_X, int L, int R, int id){
	if(L == R){
		if(is_X){
			in_X[pos] = val;
			SEGTree[id].pi_X = in_X[L];
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
			rq.modify(pos, val, 0, SIZE - 1, 1);
		}
		else{
			in_Y[pos] = val;
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		}
		return;
	}
	int M = (L + R) / 2;
	if(pos <= M)
		modify(pos, val, is_X, L, M, lc);
	else
		modify(pos, val, is_X, M + 1, R, rc);
	pull(id);
	return;
}

int init(int N, int X[], int Y[]) {
	for(int i = 0; i < N; i++){
		in_X[i] = X[i];
		in_Y[i] = Y[i];
	}
	rq.build(0, SIZE - 1, 1);
	build(0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateX(int pos, int val) {	
	modify(pos, val, 1, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateY(int pos, int val) {
	modify(pos, val, 0, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

Compilation message

horses.cpp: In function 'void pull(int)':
horses.cpp:80:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                     ^
horses.cpp:80:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:138:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 24912 KB Output is correct
2 Correct 51 ms 24976 KB Output is correct
3 Incorrect 52 ms 24912 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 25028 KB Output is correct
2 Correct 60 ms 24920 KB Output is correct
3 Incorrect 57 ms 24948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24912 KB Output is correct
2 Correct 56 ms 25168 KB Output is correct
3 Incorrect 53 ms 24920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24872 KB Output is correct
2 Correct 52 ms 24868 KB Output is correct
3 Incorrect 51 ms 25000 KB Output isn't correct
4 Halted 0 ms 0 KB -