oj.uz

Submission #64663

# Submission time Handle Problem Language Result Execution time Memory
64663 2018-08-05T10:43:45 Z FLDutchman Horses (IOI15_horses) C++14
20 / 100
 647 ms 57144 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mod = 1e9+7;

struct segtree{
	vi t;
	segtree(int N){
		t.assign(4*N, 0);
	}	

	segtree(){}

	void update(int n){
		t[n] = max(t[n<<1], t[n<<1|1]);
	}

	void modify(int i, int v, int lb, int rb, int n = 1){
		if(lb + 1 == rb) {
			t[n] = v;
			return;
		}
		int mb = (lb+rb)/2;
		if(i < mb) modify(i, v, lb, mb, n<<1);
		else modify(i, v, mb, rb, n<<1|1);
		update(n);
	}

	int rmq(int l, int r, int lb, int rb, int n = 1){
		if(lb <= l and r <= rb) return t[n];
		int mb = (lb + rb)/2;
		int res = 0;
		if(l < mb) res = max(res, rmq(l, r, lb, mb, n<<1));
		if (r > mb) res = max(res, rmq(l, r, mb, rb, n<<1|1));
		return res;
	}
};

int mpow(int a, int b){
	if(b == 0) return 1;
	if(b == 1) return a;
	if(b & 1) return a * mpow(a*a%mod, b>>1) % mod;
	return mpow(a*a%mod, b>>1);
}

int N;
vi X, Xinv, Y;
segtree tree;
multiset<int> nonunit;
int prod;

int getBest(){
	//cout << prod << endl;
	int i = N-1;
	int y = Y[i];
	int p = prod;
	while(y < mod && i > 0){
		if(X[i] == 1) {
			// precompute it and rmq?
			auto it = prev(nonunit.upper_bound(i));
			y = max(y,  tree.rmq(max(*it, 0LL), i, 0, N));
			i = *it;
		} else {
			p = p * Xinv[i] % mod;
			y = max(y * X[i], Y[i-1]);
			i--;
		}

	}
	y %= mod;
	//cout << p << " " << y << endl;
	return p * y % mod;
}

INT init(INT n, INT x[], INT y[]) {
	N = n;
	tree = segtree(N);
	prod = 1;
	nonunit.insert(-1);
	FOR(i, 0, N) Y.pb(y[i]), X.pb(x[i]), tree.modify(i, y[i], 0, N), Xinv.pb(mpow(x[i], mod-2)), prod = prod * X[i] % mod;
	FOR(i, 0, N) if(X[i] != 1) nonunit.insert(i);
	return getBest();
}

//void rem(int i){
//	nonunit.erase(i);
//
//}

INT updateX(INT pos, INT val) {	
	if(X[pos] != 1) nonunit.erase(pos);
	prod = prod * Xinv[pos] % mod * val % mod;
	X[pos] = val;
	Xinv[pos] = mpow(val, mod-2);
	if(val != 1) nonunit.insert(pos);



	return getBest();
}

INT updateY(INT pos, INT val) {
	Y[pos] = val;
	tree.modify(pos, val, 0, N);
	return getBest();
}

Compilation message

horses.cpp: In function 'INT init(INT, INT*, INT*)':
horses.cpp:96:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateX(INT, INT)':
horses.cpp:113:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateY(INT, INT)':
horses.cpp:119:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 416 KB Output is correct
2 Correct 4 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 3 ms 456 KB Output is correct
7 Incorrect 2 ms 456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Incorrect 3 ms 568 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 56480 KB Output is correct
2 Correct 606 ms 56480 KB Output is correct
3 Correct 567 ms 56960 KB Output is correct
4 Correct 647 ms 57144 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 57144 KB Output is correct
2 Correct 2 ms 57144 KB Output is correct
3 Correct 3 ms 57144 KB Output is correct
4 Correct 2 ms 57144 KB Output is correct
5 Correct 3 ms 57144 KB Output is correct
6 Correct 2 ms 57144 KB Output is correct
7 Incorrect 3 ms 57144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 57144 KB Output is correct
2 Correct 0 ms 57144 KB Output is correct
3 Correct 3 ms 57144 KB Output is correct
4 Correct 3 ms 57144 KB Output is correct
5 Correct 3 ms 57144 KB Output is correct
6 Correct 3 ms 57144 KB Output is correct
7 Incorrect 3 ms 57144 KB Output isn't correct
8 Halted 0 ms 0 KB -