Submission #127942

#	Time	Username	Problem	Language	Result	Execution time	Memory
127942		ekrem	Horses (IOI15_horses)	C++98	100 / 100	1006 ms	57428 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
ll ans[MAXN];
set < int > s;
set < int > :: iterator it;

int islem(int d, int a, int b){
	if(!d)
		return max(a, b);
	return 1ll*a*b%mod;
}

void bu(int d, int k, int bas, int son){
	if(bas == son){
		seg[d][k] = (!d)?y[bas]:x[bas];
		return;
	}
	bu(d, sol, bas, orta);
	bu(d, sag, orta + 1, son);
	seg[d][k] = islem(d, seg[d][sol], seg[d][sag]);
}

void up(int d, int k, int bas, int son, int x, int y){
	if(bas == son){
		seg[d][k] = y;
		return;
	}
	if(x <= orta)
		up(d, sol, bas, orta, x, y);
	else
		up(d, sag, orta + 1, son, x, y);
	seg[d][k] = islem(d, seg[d][sol], seg[d][sag]);
}

int qu(int d, int k, int bas, int son, int x, int y){
	if(bas > y or son < x)
		return 1;
	if(bas >= x and son <= y)
		return seg[d][k];
	return islem(d, qu(d, sol, bas, orta, x, y), qu(d, sag, orta + 1, son, x, y));
}

int ansbul(){
	if(s.size() == 2)
		return qu(0, 1, 1, n, 1, n);
	k = 0;
	ll of = 1;
	it = s.end();it--;
	while(1){
		z[++k] = *it;
		// cout << *it << endl;
		of = of*x[z[k]];
		if(it == s.begin())
			break;
		it--;
		// cout << of << endl;
		if(of > inf){
			// k--;
			break;
		}
	}
	// cout << k << endl;
	reverse(z + 1, z + k + 1);
	// for(int i = 1; i <= k; i++)cout << x[z[i]] << " ";cout << endl;
	ll crp = qu(1, 1, 1, n, 1, z[1]), mx = 1, su = 1;
	for(int i = 2; i <= k; i++){
		mx = max(mx, 1ll*ans[z[i - 1]]*su);
		su *= x[z[i]];
	}
	return (mx%mod)*crp%mod;
}

void ekle(int pos){
	s.insert(pos);
	it = s.find(pos);
	it++;
	int x = *it;
	ans[pos] = qu(0, 1, 1, n, pos, x - 1);
	it--;
	it--;
	ans[*it] = qu(0, 1, 1, n, *it, pos - 1);
}

int init(int nn, int X[], int Y[]) {n = nn;
	x[0] = x[n + 1] = 1;
	for(int i = 1; i <= n; i++){
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
	}
	bu(0, 1, 1, n);
	bu(1, 1, 1, n);
	s.insert(n + 1);
	s.insert(0);
	for(int i = 1; i <= n; i++)
		if(x[i] > 1)
			ekle(i);
	return ansbul();
}

int updateX(int pos, int val) {pos++;
	if(s.count(pos)){
		it = s.find(pos);
		it--;
		s.erase(pos);
		int x = *it;
		it++;
		ans[x] = qu(0, 1, 1, n, x, *it - 1);
	}
	x[pos] = val;
	up(1, 1, 1, n, pos, val);
	if(val > 1)
		ekle(pos);
	return ansbul();
}

int updateY(int pos, int val) {pos++;
	up(0, 1, 1, n, pos, val);
	it = s.upper_bound(pos);
	int y = *it;
	it--;
	ans[*it] = qu(0, 1, 1, n, *it, y - 1);
	return ansbul();
}

Compilation message (stderr)

horses.cpp: In function 'int islem(int, int, int)':
horses.cpp:27:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1ll*a*b%mod;
                ^
horses.cpp: In function 'void bu(int, int, int, int)':
horses.cpp:30:39: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 void bu(int d, int k, int bas, int son){
                                       ^
horses.cpp:19:8: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
        ^
horses.cpp: In function 'void up(int, int, int, int, int, int)':
horses.cpp:40:53: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void up(int d, int k, int bas, int son, int x, int y){
                                                     ^
horses.cpp:19:24: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
                        ^
horses.cpp:40:53: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void up(int d, int k, int bas, int son, int x, int y){
                                                     ^
horses.cpp:19:15: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
               ^
horses.cpp:40:53: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 void up(int d, int k, int bas, int son, int x, int y){
                                                     ^
horses.cpp:19:8: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
        ^
horses.cpp: In function 'int qu(int, int, int, int, int, int)':
horses.cpp:52:52: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 int qu(int d, int k, int bas, int son, int x, int y){
                                                    ^
horses.cpp:19:24: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
                        ^
horses.cpp:52:52: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int qu(int d, int k, int bas, int son, int x, int y){
                                                    ^
horses.cpp:19:15: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
               ^
horses.cpp:52:52: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 int qu(int d, int k, int bas, int son, int x, int y){
                                                    ^
horses.cpp:19:8: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
        ^
horses.cpp: In function 'int ansbul()':
horses.cpp:87:21: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (mx%mod)*crp%mod;
                     ^
horses.cpp: In function 'void ekle(int)':
horses.cpp:94:6: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  int x = *it;
      ^
horses.cpp:19:15: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
               ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:122:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   int x = *it;
       ^
horses.cpp:19:15: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
               ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:136:6: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  int y = *it;
      ^
horses.cpp:19:24: note: shadowed declaration is here
 int n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
                        ^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23