oj.uz

Submission #48988

# Submission time Handle Problem Language Result Execution time Memory
48988 2018-05-21T06:10:04 Z Namnamseo Horses (IOI15_horses) C++17
100 / 100
 479 ms 271832 KB 
#include "horses.h"

typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int n;
int x[500010];
int y[500010];

struct segtype {
	double t[1048576];
	double left[1048576];
	int mi[1048576];
	static const int M=524288;
	void init(){
		for(int i=0; i<2*M; ++i){
			t[i]=left[i]=-1e300;
		}
	}
	void upd(int pos,double val){
		pos+=M;
		t[pos]=val; left[pos]=val; mi[pos]=pos-M; pos>>=1;
		while(pos){
			t[pos]=t[pos*2]+t[pos*2+1];
			left[pos]=max(left[pos*2], t[pos*2]+left[pos*2+1]);
			if(left[pos*2]>t[pos*2]+left[pos*2+1]) mi[pos]=mi[pos*2];
			else mi[pos]=mi[pos*2+1];
			pos>>=1;
		}
	}
} sumt;

const int D=int(1e9)+7;

struct segint{
	static const int M=524288;
	int t[M*2];
	void init(){
		for(int i=0; i<2*M; ++i) t[i]=1;
	}
	void upd(int pos,int val){
		pos+=M; t[pos]=val; pos>>=1;
		while(pos){
			t[pos]=t[pos*2]*1LL*t[pos*2+1]%D;
			pos>>=1;
		}
	}
	int rangePi(int l,int r){
		l+=M; r+=M;
		int ret=1;
		while(l<=r){
			if(l&1) ret=(ret*1LL*t[l++])%D;
			if((r&1)==0) ret=(ret*1LL*t[r--])%D;
			l>>=1; r>>=1;
		}
		return ret;
	}
} seg_int;

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0; i<n; ++i){
		x[i]=X[i]; y[i]=Y[i];
	}
	sumt.init(); seg_int.init();
	sumt.upd(0, log(x[0]) + log(y[0]));
	seg_int.upd(0, x[0]);
	for(int i=1; i<n; ++i){
		sumt.upd(i, log(x[i])+log(y[i])-log(y[i-1]));
		seg_int.upd(i, x[i]);
	}
	int max_ind = sumt.mi[1];
	int a=seg_int.rangePi(0, max_ind);
	int b=y[max_ind];
	return a*1LL*b%D;
}

void refresh(int i){
	if(i>=n || i<0) return;
	double t=log(x[i])+log(y[i]);
	if(i) t -= log(y[i-1]);
	sumt.upd(i, t);
	seg_int.upd(i, x[i]);
}

int updateX(int pos, int val) {
	int i=pos;
	x[i]=val;
	refresh(i);
	int max_ind = sumt.mi[1];
	int a=seg_int.rangePi(0, max_ind);
	int b=y[max_ind];
	return a*1LL*b%D;
}

int updateY(int pos, int val) {
	y[pos]=val;
	refresh(pos); refresh(pos+1);
	int max_ind = sumt.mi[1];
	int a=seg_int.rangePi(0, max_ind);
	int b=y[max_ind];
	return a*1LL*b%D;
}

Compilation message

horses.cpp: In member function 'void segint::upd(int, int)':
horses.cpp:46:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    t[pos]=t[pos*2]*1LL*t[pos*2+1]%D;
           ~~~~~~~~~~~~~~~~~~~~~~~^~
horses.cpp: In member function 'int segint::rangePi(int, int)':
horses.cpp:54:32: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    if(l&1) ret=(ret*1LL*t[l++])%D;
                ~~~~~~~~~~~~~~~~^~
horses.cpp:55:37: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    if((r&1)==0) ret=(ret*1LL*t[r--])%D;
                     ~~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return a*1LL*b%D;
         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:95:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return a*1LL*b%D;
         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:104:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return a*1LL*b%D;
         ~~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21320 KB Output is correct
2 Correct 16 ms 21320 KB Output is correct
3 Correct 18 ms 21320 KB Output is correct
4 Correct 18 ms 21320 KB Output is correct
5 Correct 18 ms 21320 KB Output is correct
6 Correct 19 ms 21320 KB Output is correct
7 Correct 17 ms 21320 KB Output is correct
8 Correct 19 ms 21320 KB Output is correct
9 Correct 19 ms 21320 KB Output is correct
10 Correct 17 ms 21320 KB Output is correct
11 Correct 18 ms 21320 KB Output is correct
12 Correct 39 ms 21320 KB Output is correct
13 Correct 18 ms 21320 KB Output is correct
14 Correct 32 ms 21320 KB Output is correct
15 Correct 16 ms 21320 KB Output is correct
16 Correct 18 ms 21320 KB Output is correct
17 Correct 16 ms 21320 KB Output is correct
18 Correct 19 ms 21320 KB Output is correct
19 Correct 18 ms 21344 KB Output is correct
20 Correct 24 ms 21344 KB Output is correct
21 Correct 17 ms 21344 KB Output is correct
22 Correct 18 ms 21356 KB Output is correct
23 Correct 22 ms 21456 KB Output is correct
24 Correct 20 ms 21492 KB Output is correct
25 Correct 23 ms 21620 KB Output is correct
26 Correct 24 ms 21620 KB Output is correct
27 Correct 19 ms 21620 KB Output is correct
28 Correct 19 ms 21636 KB Output is correct
29 Correct 18 ms 21652 KB Output is correct
30 Correct 19 ms 21664 KB Output is correct
31 Correct 21 ms 21692 KB Output is correct
32 Correct 19 ms 21708 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 38104 KB Output is correct
2 Correct 445 ms 50924 KB Output is correct
3 Correct 350 ms 54540 KB Output is correct
4 Correct 440 ms 62436 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62436 KB Output is correct
2 Correct 18 ms 62436 KB Output is correct
3 Correct 22 ms 62436 KB Output is correct
4 Correct 18 ms 62436 KB Output is correct
5 Correct 20 ms 62436 KB Output is correct
6 Correct 18 ms 62436 KB Output is correct
7 Correct 18 ms 62436 KB Output is correct
8 Correct 19 ms 62436 KB Output is correct
9 Correct 19 ms 62436 KB Output is correct
10 Correct 18 ms 62436 KB Output is correct
11 Correct 19 ms 62436 KB Output is correct
12 Correct 19 ms 62436 KB Output is correct
13 Correct 23 ms 62436 KB Output is correct
14 Correct 22 ms 62436 KB Output is correct
15 Correct 18 ms 62436 KB Output is correct
16 Correct 19 ms 62436 KB Output is correct
17 Correct 20 ms 62436 KB Output is correct
18 Correct 18 ms 62436 KB Output is correct
19 Correct 17 ms 62436 KB Output is correct
20 Correct 18 ms 62436 KB Output is correct
21 Correct 17 ms 62436 KB Output is correct
22 Correct 17 ms 62436 KB Output is correct
23 Correct 51 ms 62436 KB Output is correct
24 Correct 22 ms 62436 KB Output is correct
25 Correct 20 ms 62436 KB Output is correct
26 Correct 19 ms 62436 KB Output is correct
27 Correct 20 ms 62436 KB Output is correct
28 Correct 18 ms 62436 KB Output is correct
29 Correct 19 ms 62436 KB Output is correct
30 Correct 19 ms 62436 KB Output is correct
31 Correct 22 ms 62436 KB Output is correct
32 Correct 25 ms 62436 KB Output is correct
33 Correct 238 ms 65656 KB Output is correct
34 Correct 236 ms 69508 KB Output is correct
35 Correct 300 ms 80436 KB Output is correct
36 Correct 294 ms 91328 KB Output is correct
37 Correct 239 ms 93368 KB Output is correct
38 Correct 269 ms 96480 KB Output is correct
39 Correct 224 ms 98540 KB Output is correct
40 Correct 261 ms 104304 KB Output is correct
41 Correct 231 ms 106476 KB Output is correct
42 Correct 299 ms 108572 KB Output is correct
43 Correct 252 ms 114788 KB Output is correct
44 Correct 259 ms 121228 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 121228 KB Output is correct
2 Correct 17 ms 121228 KB Output is correct
3 Correct 17 ms 121228 KB Output is correct
4 Correct 18 ms 121228 KB Output is correct
5 Correct 19 ms 121228 KB Output is correct
6 Correct 20 ms 121228 KB Output is correct
7 Correct 20 ms 121228 KB Output is correct
8 Correct 19 ms 121228 KB Output is correct
9 Correct 17 ms 121228 KB Output is correct
10 Correct 18 ms 121228 KB Output is correct
11 Correct 18 ms 121228 KB Output is correct
12 Correct 22 ms 121228 KB Output is correct
13 Correct 18 ms 121228 KB Output is correct
14 Correct 18 ms 121228 KB Output is correct
15 Correct 20 ms 121228 KB Output is correct
16 Correct 18 ms 121228 KB Output is correct
17 Correct 17 ms 121228 KB Output is correct
18 Correct 19 ms 121228 KB Output is correct
19 Correct 30 ms 121228 KB Output is correct
20 Correct 17 ms 121228 KB Output is correct
21 Correct 16 ms 121228 KB Output is correct
22 Correct 16 ms 121228 KB Output is correct
23 Correct 18 ms 121228 KB Output is correct
24 Correct 17 ms 121228 KB Output is correct
25 Correct 17 ms 121228 KB Output is correct
26 Correct 17 ms 121228 KB Output is correct
27 Correct 17 ms 121228 KB Output is correct
28 Correct 18 ms 121228 KB Output is correct
29 Correct 17 ms 121228 KB Output is correct
30 Correct 17 ms 121228 KB Output is correct
31 Correct 24 ms 121228 KB Output is correct
32 Correct 18 ms 121228 KB Output is correct
33 Correct 299 ms 126248 KB Output is correct
34 Correct 479 ms 139020 KB Output is correct
35 Correct 393 ms 142660 KB Output is correct
36 Correct 431 ms 150340 KB Output is correct
37 Correct 222 ms 153464 KB Output is correct
38 Correct 227 ms 157544 KB Output is correct
39 Correct 281 ms 168236 KB Output is correct
40 Correct 291 ms 179120 KB Output is correct
41 Correct 224 ms 181236 KB Output is correct
42 Correct 259 ms 184244 KB Output is correct
43 Correct 221 ms 186172 KB Output is correct
44 Correct 272 ms 192204 KB Output is correct
45 Correct 243 ms 194096 KB Output is correct
46 Correct 227 ms 196264 KB Output is correct
47 Correct 250 ms 202700 KB Output is correct
48 Correct 245 ms 208956 KB Output is correct
49 Correct 428 ms 214960 KB Output is correct
50 Correct 377 ms 219960 KB Output is correct
51 Correct 362 ms 231884 KB Output is correct
52 Correct 408 ms 243324 KB Output is correct
53 Correct 383 ms 246664 KB Output is correct
54 Correct 344 ms 250436 KB Output is correct
55 Correct 253 ms 252684 KB Output is correct
56 Correct 280 ms 260352 KB Output is correct
57 Correct 300 ms 263172 KB Output is correct
58 Correct 294 ms 266432 KB Output is correct
59 Correct 259 ms 271832 KB Output is correct