Submission #419137

#	Time	Username	Problem	Language	Result	Execution time	Memory
419137		AugustinasJucas	Horses (IOI15_horses)	C++14	17 / 100	366 ms	23896 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#pragma GCC optimize("O2")
#pragma GCC target("avx2")

using namespace std;
const int mod = 1e9 + 7;
struct medis{
	struct node{
		int l, r;
		int sand = 1;
		int vntCnt = 0;
		int maxY = 0;
	};
	int n;
	int dbInd = 0;
	vector<node> tree;
	void build(int v){
		if(v >= n){
			tree[v].l = tree[v].r = dbInd++;
		}else{
			build(v*2); build(v*2+1);
			tree[v].l = tree[v*2].l;
			tree[v].r = tree[v*2+1].r;
		}
	}
	medis(int dd){
		n = dd;
		tree.resize(2*n+1);
		build(1);
	}
	void changeX(int v, int l, int r, int x){
		if(l <= tree[v].l && tree[v].r <= r){
			tree[v].sand = x;
			tree[v].vntCnt = (x == 1);
		}else if(r < tree[v].l || tree[v].r < l){
			return;
		}else{
			changeX(v*2, l, r, x);
			changeX(v*2+1, l, r, x);
			tree[v].sand = tree[v*2].sand * tree[v*2+1].sand % mod;
			tree[v].vntCnt = tree[v*2].vntCnt + tree[v*2+1].vntCnt;
		}
	}
	void changeY(int v, int l, int r, int x){
		if(l <= tree[v].l && tree[v].r <= r){
			tree[v].maxY = x;
		}else if(r < tree[v].l || tree[v].r < l){
			return;
		}else{
			changeY(v*2, l, r, x);
			changeY(v*2+1, l, r, x);
			tree[v].maxY = max(tree[v*2].maxY, tree[v*2+1].maxY);
		}
	}
	int getSand(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].sand;
		}else if(r < tree[v].l || tree[v].r < l){
			return 1;
		}else{
			return 1ll * getSand(v*2, l, r) * getSand(v*2+1, l, r) % mod;
		}
	}
	int getMax(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].maxY;
		}else if(r < tree[v].l || tree[v].r < l){
			return 1;
		}else{
			return max(getMax(v*2, l, r), getMax(v*2+1, l, r));
		}
	}
	int get1(int v, int l, int r){
		if(l <= tree[v].l && tree[v].r <= r){
			return tree[v].vntCnt;
		}else if(r < tree[v].l || tree[v].r < l){
			return 0;
		}else{
			return get1(v*2, l, r) + get1(v*2+1, l, r);
		}
	}
};
const int dydis = 5e5 + 10;
medis tree(dydis);
int n;
int r = 0;
int l = 0;
int mid = 0;
int kk = 0;
pair<int, vector<pair<long long, long long> > > last30(int n){
	int lastNotIn = n-1;
	vector<pair<long long, long long> > ret;

	for(int i = 0; i < 62; i++){
		if(lastNotIn == -1) break;
		if(tree.getSand(1, lastNotIn, lastNotIn) == 1){
			int rt = lastNotIn;
			l = 0; r = lastNotIn;
		//	cout << "l = " << l << ", r = " << r << endl;
			while(l <= r){
				mid = (l + r) / 2;
				if(tree.get1(1, mid, lastNotIn) == lastNotIn-mid+1){
					rt = min(rt, mid);
		//			cout << mid  << " tinka " << endl;
					r = mid-1;
				}else{
					l = mid+1;
				}
			}
			ret.push_back({1, tree.getMax(1, rt, lastNotIn)});
			lastNotIn = rt-1;
		}else{
			ret.push_back({tree.getSand(1, lastNotIn, lastNotIn), tree.getMax(1, lastNotIn, lastNotIn)});
			lastNotIn--;
			kk++;
		}
		if(kk > 31) break;
	}
	reverse(ret.begin(), ret.end());
	long long bv = 1;
	if(lastNotIn != -1) bv = tree.getSand(1, 0, lastNotIn);
	return {bv, ret};
}


long long get(){
	auto rk = last30(n);
	auto mas = rk.second;
//	cout << "h = " << h << ", poros: "; for(auto x : mas) cout << "{" << x.first << ", " << x.second << "},  ";
//	cout <<endl << endl;
	int curMax = 0;
	long long B;
	long long turiButi;
	bool did;
	for(int i = 0; i < (int)mas.size(); i++){
		B = 1;
		//cout << "i = " << i << endl;
		
		did = 0;
		for(int j = i+1; j < (int) mas.size(); j++){
			B *= mas[j].first;
			if(mas[j].second >= mas[i].second){
			//	cout << "STAS!" << endl;
				curMax = j;
				did = 1;
				i = j-1; break;
			}
			turiButi = mas[i].second / mas[j].second + 1;
		//	cout << "turi buti bent " << turiButi << ", o B = " << B << endl;
			if(B >= turiButi){
			//	cout << "tai, daray suita!" << endl;
				i = j-1;
				did = 1;
				curMax = j;
				break;
			}
		}
		if(!did) break;

	}
	long long ret = rk.first;
	for(int i = 0; i <= curMax; i++){
		ret = ret * mas[i].first % mod;
	}
	ret = ret * mas[curMax].second % mod;
	return ret;
}


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0; i < n; i++){
		tree.changeX(1, i, i, X[i]);
		tree.changeY(1, i, i, Y[i]);
	}
	
	return get();
}

int updateX(int pos, int val) {	
	tree.changeX(1, pos, pos, val);
	return get();
}

int updateY(int pos, int val) {
	tree.changeY(1, pos, pos, val);
	return get();
}

Compilation message (stderr)

horses.cpp: In member function 'int medis::getSand(int, int, int)':
horses.cpp:62:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   62 |    return 1ll * getSand(v*2, l, r) * getSand(v*2+1, l, r) % mod;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'std::pair<int, std::vector<std::pair<long long int, long long int> > > last30(int)':
horses.cpp:91:60: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   91 | pair<int, vector<pair<long long, long long> > > last30(int n){
      |                                                        ~~~~^
horses.cpp:86:5: note: shadowed declaration is here
   86 | int n;
      |     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:178:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  178 |  return get();
      |         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:183:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  183 |  return get();
      |         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:188:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  188 |  return get();
      |         ~~~^~

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