oj.uz

Submission #818070

# Submission time Handle Problem Language Result Execution time Memory
818070 2023-08-10T01:33:10 Z vjudge1 Poklon (COCI17_poklon) C++17
84 / 140
 5000 ms 17084 KB 
#include <bits/stdc++.h>

using namespace std;
#define N 500007
int n,q,l,r,cnt[N],a[N],dp[N];
vector<pair<int,int>> b;
vector<pair<pair<int,int>,int>> res;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        b.push_back({a[i],i});
    }
    sort(b.begin(),b.end());
    int tmp=0;
    for (int i=0; i<n; i++)
    {
        if(i==0 || b[i].first!=b[i-1].first) tmp++;
        a[b[i].second]=tmp;
    }
    for(int i=1; i<=q; i++)
    {
        cin >> l >> r;
        res.push_back({{l,r},i});
    }
    sort(res.begin(),res.end());
    int l=0,r=0,ans=0;
    for (auto c:res)
    {
//        cout << c.first.first << " " << c.first.second <<"\n";
        for(int i=r+1;i<=c.first.second; i++)
        {
            cnt[a[i]]++;
            if (cnt[a[i]]==3) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=max(r,c.first.second);
//        cout << ans << "\n";
        for (int i=l; i<c.first.first; i++)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        l=max(l,c.first.first);
//        cout << ans << "\n";
        for (int i=r; i>c.first.second; i--)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=min(r,c.first.second);
//        cout << ans << "\n";
        dp[c.second]=ans;
    }
    for(int i=1; i<=q; i++) cout << dp[i] << "\n";
    return 0;
}

Subtask #1
84.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 2435 ms 3984 KB Output is correct
6 Correct 2408 ms 3980 KB Output is correct
7 Execution timed out 5072 ms 7352 KB Time limit exceeded
8 Execution timed out 5083 ms 13052 KB Time limit exceeded
9 Execution timed out 5082 ms 14300 KB Time limit exceeded
10 Execution timed out 5055 ms 17084 KB Time limit exceeded