제출 #419153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419153		AugustinasJucas	말 (IOI15_horses)	C++14	57 / 100	1580 ms	38732 KiB

horses

#include <bits/stdc++.h>
//#include "horses.h"
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
 
using namespace std;
const long long mod = 1e9 + 7;
struct medis{
	struct node{
		int l, r;
		int sand = 1;
		int vntCnt = 0;
		long long 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 = 1ll * 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;
		}
	}
	long long 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);
		}
	}
	int fd(int v, int sm){ // rasti kairiausia x, kad suf[x; n] <= sm
		if(tree[v].l == tree[v].r){
			if(tree[v].vntCnt == 1 && sm == 0) return tree[v].l + 1;
			return tree[v].l;
		}
		//cout << "esu [" << tree[v].l << "; " << tree[v].r << "], cia sk = " << tree[v].vntCnt << ", o ieskau " << sm << endl;
		if(tree[v*2+1].vntCnt < sm){
			return fd(v*2, sm-tree[v*2+1].vntCnt);
		}else if(tree[v*2+1].vntCnt == sm){
			return fd(v*2, sm-tree[v*2+1].vntCnt);
		}else{
		//	cout << "darau sita " << endl;
			return fd(v*2+1, sm);
		}
		
	}
};
const int dydis = 5e5 + 10;
medis tree(dydis);
int n;
pair<int, vector<pair<long long, long long> > > last30(int n){
	int lastNotIn = n-1;
	vector<pair<long long, long long> > ret;
	//cout << "n = " << n << endl;
	int r = 0;
	int l = 0;
	int mid = 0;
	int kk = 0;
	for(int i = 0; i < 62; i++){
		if(lastNotIn == -1) break;
		//cout << "imu " << lastNotIn << endl;
		if(tree.getSand(1, lastNotIn, lastNotIn) == 1){
			int rt = lastNotIn;
			l = 0; r = lastNotIn;
			//cout << lastNotIn << " yra 1 " << endl;
		//	cout << "l = " << l << ", r = " << r << endl;
			int tr = tree.get1(1, lastNotIn, dydis-1);
			//cout << "tr = " << tr << endl;
	//		cout << endl;
			rt = tree.fd(1, tr);
			//cout << "rt randu kaip " << rt << ", nes ieskojau " << tr << 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);
	long long h = rk.first;
	auto mas = rk.second;
	//cout << "h = " << h << ", poros: "; for(auto x : mas) cout << "{" << x.first << ", " << x.second << "},  ";
	//cout <<endl << endl;
	int curMax = 0;
	for(int i = 0; i < (int)mas.size(); i++){
		long long B = 1;
		//cout << "i = " << i << endl;
		bool 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;
			}
			long long 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 = h;
	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();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In member function 'void medis::changeX(int, int, int, int)':
horses.cpp:41:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   41 |    tree[v].sand = 1ll * tree[v*2].sand * tree[v*2+1].sand % mod;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
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:103:60: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  103 | pair<int, vector<pair<long long, long long> > > last30(int n){
      |                                                        ~~~~^
horses.cpp:102:5: note: shadowed declaration is here
  102 | int n;
      |     ^
horses.cpp:107:6: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  107 |  int r = 0;
      |      ^
horses.cpp:108:6: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  108 |  int l = 0;
      |      ^
horses.cpp:109:6: warning: unused variable 'mid' [-Wunused-variable]
  109 |  int mid = 0;
      |      ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:198:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  198 |  return get();
      |         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:203:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  203 |  return get();
      |         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:208:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  208 |  return get();
      |         ~~~^~

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