Submission #378407

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378407	2021-03-16T17:20:41 Z	limabeans	Po (COCI21_po)	C++17	70 / 70	50 ms	13668 KB

Main

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







const int inf = 2e9;

struct sparse_table {

    const static int LOG = 20;
    int n;
    vector<int> a[LOG+1];
    vector<int> lg_floor;

    int eval(int x, int y) {
	return min(x, y);
    }

    void init(vector<int> v) {
	n = v.size();
	lg_floor.resize(n+10);
	lg_floor[1] = 0;
	for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
	for (int j=0; j<LOG; j++) a[j].resize(n);
	for (int i=0; i<n; i++) a[0][i] = v[i];
	

	for (int j=1; j<LOG; j++) {
	    for (int i=0; i<n; i++) {
		a[j][i] = a[j-1][i];
		if (i + (1<<(j-1)) < n) {
		    a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
		}
	    }
	}
    }

    int get(int l, int r) {
	if (l>r) {
	    return inf;   
	}
	int lg = lg_floor[r - l + 1];

	return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
	
    }
};

int n;
vector<int> a;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    a.resize(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    sparse_table rmq;
    rmq.init(a);
    
    int res = n;
    for (int i=0; i<n; i++) {
	if (a[i] == 0) {
	    res--;
	}
    }

    map<int,int> last;

    for (int i=0; i<n; i++) {
	if (a[i] != 0) {
	    if (last.count(a[i])) {
		int j = last[a[i]];
		if (rmq.get(j+1,i-1) > a[i]) {
		    res--;
		}
	    
	    }
	    last[a[i]] = i;
	}
    }

    cout<<res<<endl;
    return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	11 ms	4844 KB	Output is correct
5	Correct	18 ms	7148 KB	Output is correct
6	Correct	50 ms	11364 KB	Output is correct
7	Correct	49 ms	13668 KB	Output is correct