# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
393007 | sumit_kk10 | Po (COCI21_po) | C++14 | 162 ms | 19916 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
int n, a[N];
long long seg_tree[4 * N];
void build(int vertex, int l, int r){
if(l > r) return;
if(l == r){
seg_tree[vertex] = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * vertex, l, mid);
build(2 * vertex + 1, mid + 1, r);
seg_tree[vertex] = min(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]);
}
ll querry(ll node, ll st, ll end, ll l, ll r){
if(st > end || l > r || st > r || end < l) return INT_MAX;
if(l <= st && end <= r) return seg_tree[node];
ll mid = (st + end) >> 1;
ll t = querry(node * 2, st, mid, l, r);
ll tt = querry(node * 2 + 1, mid + 1, end, l, r);
return min(t, tt);
}
bool cmp(pair<int, vector<int> > a, pair<int, vector<int> > b){
return a.first < b.first;
}
vector<pair<int, vector<int> > > sort1(map<int, vector<int> >& M){
vector<pair<int, vector<int> > > A;
for (auto& it : M)
A.push_back(it);
sort(A.begin(), A.end(), cmp);
return A;
}
int main(){
fast;
cin >> n;
map<int, vector<int> > pos;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(a[i] != 0)
pos[a[i]].push_back(i);
}
build(1, 1, n + 1);
long long res = 0;
vector<pair<int, vector<int> > > ans = sort1(pos);
for(auto k : ans){
++res;
for(int i = 1; i < k.second.size(); ++i){
int pre = k.second[i - 1], now = k.second[i];
int mn = querry(1, 1, n + 1, pre, now);
// cout << k.first << ' ' << mn << '\n';
if(mn < k.first)
++res;
}
}
cout << res << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |