Submission #857086

#	Time	Username	Problem	Language	Result	Execution time	Memory
857086		Onur_Ilgaz	OGLEDALA (COI15_ogledala)	C++17	19 / 100	1290 ms	524288 KiB

ogledala

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
int m, n, q;
vector <int> points, interval;
set <int> found;
vector <int> numbers, all;
vector <vector<pair<int, int> > > dp, sayi; // [numberindex][nomeaning]
											// {includesthisindex, with this freq}

void findnumbers(int x) {
	if(x == 0) return;
	found.insert(x);
	int f = (x - 1) / 2, s = x / 2;
	if(!found.count(f)) findnumbers(f);
	if(x % 2 == 0 and !found.count(s)) findnumbers(s);
}

int find(int x) {
	return (lower_bound(numbers.begin(), numbers.end(), x) - numbers.begin());
}

int finding(int dpindex, int search) {
	int l = 0, r = dp[dpindex].size();
	while(r - l > 1) {
		int m = (r + l) / 2;
		if(dp[dpindex][m].first > search) {
			r = m;
		}
		else {
			l = m;
		}
	}
	return l;
}

void calc(int numindex) {
	int x = numbers[numindex];
	int f = (x - 1) / 2, s = x / 2;
	if(x == 2) {
		dp[numindex] = dp[find(f)];
	}
	if(x <= 2) {
		dp[numindex].push_back({numindex, 1});
		return;
	}
	if(x % 2) {
		for(auto &[index, val]:dp[find(f)]) {
			dp[numindex].push_back({index, val * 2});
		}
	}
	else {
		vector <pair<int, int> > tempv = dp[find(f)];
		for(auto &[index, val]:dp[find(s)]) {
			tempv.push_back({index, val});
		}
		sort(tempv.begin(), tempv.end());
		for(int i = 0; i < tempv.size(); i++){
			int val = tempv[i].second;
			if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
				val += tempv[i + 1].second;
				i++;
			}	
			dp[numindex].push_back({tempv[i].first, val});
		}
	}
	dp[numindex].push_back({numindex, 1});
}

int32_t main(){
	fast
	cin>>m>>n>>q;
	points.push_back(0);
	for(int i = 1; i <= n; i++) {
		int in;
		cin>>in;
		points.push_back(in);
	}
	points.push_back(m + 1);
	for(int i = 0; i <= n; i++) {
		interval.push_back(points[i + 1] - points[i] - 1);
		findnumbers(interval[i]);
	}
	dp.resize(found.size());
	all.resize(found.size());
	sayi.resize(found.size());
	for(auto it:found) {
		numbers.push_back(it);
		calc(numbers.size() - 1);
	}
	for(int i = 0; i <= n; i++) {
		int st = points[i], length = interval[i];
		if(length == 0) continue;
		for(auto &[index, freq]:dp[find(length)]) {
			all[index] += freq;
			sayi[index].push_back({i, freq});
		}
	}
	// int time = 0;
	// for(auto it:sayi) {
	// 	cout<<numbers[time]<<":\n";
	// 	for(auto itt:it) {
	// 		cout<<itt.first<<" "<<itt.second<<"\n";
	// 	}
	// 	time++;
	// }
	int allindex = numbers.size() - 1, sayindex = 0, gone = 0; 
	for(int i = 0; i < q; i++) {
		int query;
		cin>>query;
		if(query <= n) {
			cout<<points[query]<<"\n";
			continue;
		}
		query -= n;
		int rem = query - gone, val;
		while(true) {
			val = sayi[allindex][sayindex].second;
			if(val >= rem) break;
			gone += val;
			rem -= val;
			sayindex++;
			if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
		}
		int intervalIndex = sayi[allindex][sayindex].first;
		// use rem to navigate inside the interval
		val = interval[intervalIndex];
		int stpoint = points[intervalIndex];
		int add = 0;
		// allindexe göre searchla
		// cout<<numbers[allindex]<<":\n";
		while(val > numbers[allindex]) {
			// cout<<val<<" "<<add<<" "<<rem<<"\n";
			int f = (val - 1) / 2, s = val / 2;
			int findex = find(f);
			int underindex = finding(findex, allindex);
			if(!f or dp[findex][underindex].first != allindex) {
				// cout<<"right1\n";
				add += f + 1;
				val = s;
				continue;
			}
			int leftfreq = dp[findex][underindex].second;
			if(leftfreq >= rem) {
				// cout<<"left\n";
				val = f;
			}
			else {
				// cout<<"right\n";
				add += f + 1;
				rem -= leftfreq;
				val = s;
			}
		}
		// cout<<val<<"\n";
		add += (val - 1) / 2;
		cout<<add + stpoint + 1<<"\n";
	}

}

Compilation message (stderr)

ogledala.cpp: In function 'void calc(long long int)':
ogledala.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i = 0; i < tempv.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
ogledala.cpp:63:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    if(i < tempv.size() - 1 and tempv[i].first == tempv[i + 1].first) {
      |       ~~^~~~~~~~~~~~~~~~~~
ogledala.cpp: In function 'int32_t main()':
ogledala.cpp:95:7: warning: unused variable 'st' [-Wunused-variable]
   95 |   int st = points[i], length = interval[i];
      |       ^~
ogledala.cpp:126:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |    if(sayindex == sayi[allindex].size()) allindex--, sayindex = 0;
      |       ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59