Submission #386264

#	Time	Username	Problem	Language	Result	Execution time	Memory
386264		patrikpavic2	Money (IZhO17_money)	C++17	100 / 100	326 ms	17132 KiB

money

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 1e6 + 500;

int A[N], n, prv[N], nxt[N], sol;
int cnt[N];

void remove(int x){
	prv[nxt[x]] = prv[x];
	nxt[prv[x]] = nxt[x];
}

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		cnt[A[i]]++;
	}
	for(int i = 1;i < N;i++){
		prv[i] = i - 1;
		nxt[i - 1] = i;
	}
	for(int i = n - 1;i >= 0;i--){
		cnt[A[i]]--;
		while(i > 0 && A[i - 1] == A[i]){
			i--; cnt[A[i]]--;
		}
		int cur = prv[A[i]]; 
		while(!cnt[cur] && cur > 0) {
			remove(cur); cur = prv[cur];
		}
		if(i > 0 && A[i - 1] == cur){
			i--; cnt[A[i]]--;
		}
		cur = A[i];
		while(!cnt[cur] && cur > 0) {
			remove(cur); cur = prv[cur];
		}
		while(i > 0 && A[i - 1] == cur){
			i--; cnt[A[i]]--;
			while(!cnt[cur] && cur > 0) {
				remove(cur); cur = prv[cur];
			}
		}
		sol++;
	}
	printf("%d\n", sol);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
money.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55