Submission #393007

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393007	2021-04-22T14:09:14 Z	sumit_kk10	Po (COCI21_po)	C++14	70 / 70	162 ms	19916 KB

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

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

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

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	18 ms	1996 KB	Output is correct
5	Correct	29 ms	3452 KB	Output is correct
6	Correct	113 ms	11312 KB	Output is correct
7	Correct	162 ms	19916 KB	Output is correct