oj.uz

Submission #43592

# Submission time Handle Problem Language Result Execution time Memory
43592 2018-03-18T04:21:20 Z gnoor Horses (IOI15_horses) C++14
17 / 100
 192 ms 146384 KB 
#include "horses.h"
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

const int mod = 1000000007;

struct number {
	long long val;
	bool overflow;
	number() {
		val=0;
		overflow=false;
	}
	number(long long _val) {
		val=_val;
		overflow=false;
	}

	number(long long _val,bool _of) {
		val=_val;
		overflow=_of;
	}
	bool operator< (const number &r) const {
		if (overflow||r.overflow) {
			return r.overflow;
		}
		return val<r.val;
	}

	number operator+(const number &r) const {
		return number((val+r.val)%mod,(val+r.val)>=mod||overflow||r.overflow);
	}
	number operator-(const number &r) const {
		return number(((val-r.val)%mod+mod)%mod,(val-r.val)<0||overflow||r.overflow);
	}
	number operator*(const number &r) const {
		return number((val*r.val)%mod,(val*r.val)>=mod||overflow||r.overflow);
	}
	number& operator=(const long long _val) {
		val=_val%mod;
		overflow=_val>=mod;
		return *this;
	}
};

struct node {
	number xval;
	number ymax;
	number pre;
	number suf;	
	void combine(const node &l,const node &r) {
		xval=l.xval*r.xval;
		if (l.ymax<l.suf*r.pre*r.ymax) {
			//choose right
			ymax=r.ymax;
			pre=l.xval*r.pre;
			suf=r.suf;
		} else {
			//choose left
			ymax=l.ymax;
			pre=l.pre;
			suf=l.suf*r.xval;	
		}
	}
};

node seg[2000100];
number x[500100];
number y[500100];
int n;

void build(int idx,int l,int r) {
	if (l+1==r) {
		seg[idx].xval=x[l];
		seg[idx].pre=x[l];
		seg[idx].suf=1;
		seg[idx].ymax=y[l];
		return;
	}					
	int m=(l+r)>>1;
	build(idx*2+1,l,m);
	build(idx*2+2,m,r);
	seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}

void update(int idx,int l,int r,int k) {
	if (k<l||k>=r) return;
	if (l+1==r) {
		seg[idx].xval=x[l];
		seg[idx].pre=x[l];
		seg[idx].suf=0;
		seg[idx].ymax=y[l];
		return;
	}
	int m=(l+r)>>1;
	update(idx*2+1,l,m,k);
	update(idx*2+2,m,r,k);
	seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}

//void print(int idx,int l,int r) {
	//printf("%d %d: %lld %lld %lld %lld\n",l,r,seg[idx].xval.val,seg[idx].ymax.val,seg[idx].suf.val,seg[idx].pre.val);
	//if (l+1==r) return;
	//int m=(l+r)>>1;
	//print(idx*2+1,l,m);
	//print(idx*2+2,m,r);
//}

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];
	}
	build(0,0,n);
	//print(0,0,n);
	return (seg[0].pre*seg[0].ymax).val;
}

int updateX(int pos, int val) {	
	x[pos]=val;
	update(0,0,n,pos);
	return (seg[0].pre*seg[0].ymax).val;
}

int updateY(int pos, int val) {
	y[pos]=val;
	update(0,0,n,pos);
	return (seg[0].pre*seg[0].ymax).val;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:126:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:132:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (seg[0].pre*seg[0].ymax).val;
                                  ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 141176 KB Output is correct
2 Correct 98 ms 141284 KB Output is correct
3 Correct 103 ms 141284 KB Output is correct
4 Correct 105 ms 141368 KB Output is correct
5 Correct 103 ms 141372 KB Output is correct
6 Correct 104 ms 141372 KB Output is correct
7 Correct 104 ms 141372 KB Output is correct
8 Correct 100 ms 141404 KB Output is correct
9 Correct 102 ms 141536 KB Output is correct
10 Correct 100 ms 141536 KB Output is correct
11 Correct 102 ms 141548 KB Output is correct
12 Correct 100 ms 141548 KB Output is correct
13 Correct 102 ms 141548 KB Output is correct
14 Correct 97 ms 141548 KB Output is correct
15 Correct 99 ms 141548 KB Output is correct
16 Correct 98 ms 141548 KB Output is correct
17 Correct 101 ms 141548 KB Output is correct
18 Correct 98 ms 141548 KB Output is correct
19 Correct 98 ms 141548 KB Output is correct
20 Correct 98 ms 141548 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 141548 KB Output is correct
2 Correct 100 ms 141548 KB Output is correct
3 Correct 105 ms 141548 KB Output is correct
4 Correct 109 ms 141548 KB Output is correct
5 Correct 103 ms 141548 KB Output is correct
6 Correct 99 ms 141548 KB Output is correct
7 Correct 100 ms 141548 KB Output is correct
8 Correct 101 ms 141548 KB Output is correct
9 Correct 103 ms 141548 KB Output is correct
10 Correct 99 ms 141548 KB Output is correct
11 Correct 107 ms 141548 KB Output is correct
12 Correct 99 ms 141548 KB Output is correct
13 Correct 104 ms 141548 KB Output is correct
14 Correct 102 ms 141588 KB Output is correct
15 Correct 98 ms 141588 KB Output is correct
16 Correct 99 ms 141588 KB Output is correct
17 Correct 99 ms 141588 KB Output is correct
18 Correct 102 ms 141588 KB Output is correct
19 Correct 102 ms 141588 KB Output is correct
20 Correct 101 ms 141588 KB Output is correct
21 Incorrect 98 ms 141588 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 146384 KB Output is correct
2 Correct 99 ms 146384 KB Output is correct
3 Correct 102 ms 146384 KB Output is correct
4 Correct 101 ms 146384 KB Output is correct
5 Correct 103 ms 146384 KB Output is correct
6 Correct 98 ms 146384 KB Output is correct
7 Correct 99 ms 146384 KB Output is correct
8 Correct 101 ms 146384 KB Output is correct
9 Correct 101 ms 146384 KB Output is correct
10 Correct 100 ms 146384 KB Output is correct
11 Correct 120 ms 146384 KB Output is correct
12 Correct 99 ms 146384 KB Output is correct
13 Correct 99 ms 146384 KB Output is correct
14 Correct 99 ms 146384 KB Output is correct
15 Correct 104 ms 146384 KB Output is correct
16 Correct 99 ms 146384 KB Output is correct
17 Correct 99 ms 146384 KB Output is correct
18 Correct 97 ms 146384 KB Output is correct
19 Correct 100 ms 146384 KB Output is correct
20 Correct 99 ms 146384 KB Output is correct
21 Incorrect 102 ms 146384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 146384 KB Output is correct
2 Correct 103 ms 146384 KB Output is correct
3 Correct 122 ms 146384 KB Output is correct
4 Correct 99 ms 146384 KB Output is correct
5 Correct 100 ms 146384 KB Output is correct
6 Correct 102 ms 146384 KB Output is correct
7 Correct 100 ms 146384 KB Output is correct
8 Correct 99 ms 146384 KB Output is correct
9 Correct 99 ms 146384 KB Output is correct
10 Correct 101 ms 146384 KB Output is correct
11 Correct 100 ms 146384 KB Output is correct
12 Correct 99 ms 146384 KB Output is correct
13 Correct 107 ms 146384 KB Output is correct
14 Correct 100 ms 146384 KB Output is correct
15 Correct 100 ms 146384 KB Output is correct
16 Correct 101 ms 146384 KB Output is correct
17 Correct 98 ms 146384 KB Output is correct
18 Correct 99 ms 146384 KB Output is correct
19 Correct 112 ms 146384 KB Output is correct
20 Correct 104 ms 146384 KB Output is correct
21 Incorrect 106 ms 146384 KB Output isn't correct
22 Halted 0 ms 0 KB -