Submission #392987

#	Time	Username	Problem	Language	Result	Execution time	Memory
392987		sumit_kk10	Po (COCI21_po)	C++14	20 / 70	54 ms	13636 KiB

Main

#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);
}

int main(){
    fast;
    cin >> n;
    map<int, vector<int> > pos;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    build(1, 1, n + 1);
    long long ans = 0;
    for(auto k : pos){
        ++ans;
        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)
                ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 1; i < k.second.size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 70