Submission #572140

#	Time	Username	Problem	Language	Result	Execution time	Memory
572140		beaconmc	Horses (IOI15_horses)	C++14	57 / 100	388 ms	81208 KiB

horses

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double
#define SIZE 1048576
#define HSIZE 524288
#define MOD 1000000007
// #include "horses.h"
using namespace std;

vector<ll> x, y, xx, yy;
ll n;


ll tree[SIZE];
ll tree2[SIZE];

set<vector<ll>> ranges;

void update(ll a,ll b){
    a += HSIZE;
    tree[a] = b;
    while (a>1){
        a/=2;
        tree[a] = tree[a*2]*tree[a*2+1]%MOD;
    }
}
void update2(ll a,ll b){
    a += HSIZE;
    tree2[a] = b;
    while (a>1){
        a/=2;
        tree2[a] = max(tree2[a*2], tree2[a*2+1]);
    }
}

ll query(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 1;
    while (a<=b){
        if (a%2==1){
            maxi *= tree[a++]; 
            maxi %= MOD;
        }
        if (b%2==0){
            maxi *= tree[b--];
            maxi %= MOD;
        }
        a/=2; b/=2;
    }
    return maxi;
}
ll query2(ll a, ll b){
    a += HSIZE;
    b += HSIZE;
    ll maxi = 0;
    while (a<=b){
        if (a%2==1){
            maxi = max(maxi, tree2[a++]); 
        }
        if (b%2==0){
            maxi = max(maxi, tree2[b--]);
        }
        a/=2; b/=2;
    }
    return maxi;
}




int solve(){

	vector<ll> xx;
	vector<ll> yy;
	vector<ll> pos;

	ll cur = 31;
	auto it = ranges.end();

	while (cur--){
		it--;
		xx.push_back(x[(*it)[0]]);
		yy.push_back(query2((*it)[0], (*it)[1]));
		pos.push_back((*it)[0]);
		if (it==ranges.begin()){
			break;
		}
	}
	reverse(xx.begin(), xx.end());
	reverse(yy.begin(), yy.end());
	reverse(pos.begin(), pos.end());

	cur = 1;
	ll maxsum = 1;
	ll maxpos = -1;

	FOR(i,0, xx.size()){
		cur *= xx[i];

		if (cur >= maxsum/yy[i]){
			cur = 1;
			maxsum = yy[i];
			maxpos = i;
		}
	}

	int realsus = (query(0, pos[maxpos]) * maxsum) % 1000000007;


	return realsus;

}

int init(int N, int X[], int Y[]) {
	n = N;
	FOR(i,0,N){
		x.push_back(X[i]);
		update(i, X[i]);
		y.push_back(Y[i]);
		update2(i, Y[i]);
	}
	ll prev = -1;

	FORNEG(i, n-1, -1){
		if (x[i] == 1 && prev==-1){
			prev = i;
		}

		if (x[i] != 1){
			if (prev != -1){
				ranges.insert({i, prev});
				prev = -1;
			}else{
				ranges.insert({i,i});
			}
		}
	}


	if (prev != -1){
		ranges.insert({0, prev});
	}


	return solve();

}

int updateX(int pos, int val) {
	if (x[pos] == val) return solve();
	update(pos, val);
	if (pos!=0){
		if (x[pos] == 1 && val != 1){
			auto it = ranges.upper_bound({pos, 9999999999});
			it--;
			vector<ll> first = *it;
			ranges.insert({first[0], pos-1});
			ranges.insert({pos, first[1]});
			ranges.erase(it);
		}


		if (x[pos] != 1 && val == 1){
			auto it = ranges.upper_bound({pos, 9999999999});
			it--;
			vector<ll> first = *it;
			it --;
			vector<ll> second = *it;
			ranges.erase(first);ranges.erase(second);
			ranges.insert({second[0], first[1]});
		}
	}


	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {

	update2(pos, val);
	y[pos] = val;
	return solve();

}

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:78:13: warning: declaration of 'xx' shadows a global declaration [-Wshadow]
   78 |  vector<ll> xx;
      |             ^~
horses.cpp:14:18: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                  ^~
horses.cpp:79:13: warning: declaration of 'yy' shadows a global declaration [-Wshadow]
   79 |  vector<ll> yy;
      |             ^~
horses.cpp:14:22: note: shadowed declaration is here
   14 | vector<ll> x, y, xx, yy;
      |                      ^~
horses.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  102 |  FOR(i,0, xx.size()){
      |      ~~~~~~~~~~~~~~              
horses.cpp:102:2: note: in expansion of macro 'FOR'
  102 |  FOR(i,0, xx.size()){
      |  ^~~
horses.cpp:112:49: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  int realsus = (query(0, pos[maxpos]) * maxsum) % 1000000007;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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