Submission #1273045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273045		SmuggingSpun	Po (COCI21_po)	C++20	20 / 70	91 ms	27884 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 1e5 + 5;
int lgv[lim], spt[lim][17];
map<int, vector<int>>pos;
int get_min(int l, int r){
	int k = lgv[r - l + 1];
	return min(spt[l][k], spt[r - (1 << k) + 1][k]);
}
int solve(int l, int r){
	if(l > r){
		return 0;
	}
	if(l == r){
		return 1;
	}
	int v = get_min(l, r), ans = 1;
	for(int i = lower_bound(pos[v].begin(), pos[v].end(), l) - pos[v].begin(); i < pos[v].size() && pos[v][i] <= r; i++){
		ans += solve(l, pos[v][i] - 1);
		l = pos[v][i] + 1;
	}
	return ans + solve(l, r);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n;
	cin >> n;
	lgv[0] = -1;
	for(int i = 1; i <= n; i++){
		cin >> spt[i][0];
		pos[spt[i][0]].emplace_back(i);
		lgv[i] = lgv[i >> 1] + 1;
	}
	for(int j = 1; j < 17; j++){
		for(int i = 1; i + (1 << j) - 1 <= n; i++){
			spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
		}
	}
	cout << solve(1, n);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 70