oj.uz

답안 #64656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64656 2018-08-05T10:25:09 Z FLDutchman 말 (IOI15_horses) C++14
20 / 100
 1500 ms 57980 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;
set<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) {
			auto it = nonunit.lower_bound(i);
			y = max(y*X[i],  tree.rmq(*it+1, i+1, 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();
}

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:95: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:104: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:110:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Execution timed out 1564 ms 488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 488 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Execution timed out 1577 ms 488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 457 ms 56288 KB Output is correct
2 Correct 659 ms 56456 KB Output is correct
3 Correct 570 ms 57980 KB Output is correct
4 Correct 701 ms 57980 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 57980 KB Output is correct
2 Correct 3 ms 57980 KB Output is correct
3 Execution timed out 1561 ms 57980 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 57980 KB Output is correct
2 Correct 4 ms 57980 KB Output is correct
3 Execution timed out 1567 ms 57980 KB Time limit exceeded
4 Halted 0 ms 0 KB -