oj.uz

Submission #818078

# Submission time Handle Problem Language Result Execution time Memory
818078 2023-08-10T01:42:27 Z vjudge1 Poklon (COCI17_poklon) C++14
84 / 140
 5000 ms 17332 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=1;
    a[b[0].second]=tmp;
    for (int i=1; i<n; i++)
    {
        if(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 (int j=0; j<q; j++)
    {
//        cout << c.first.first << " " << c.first.second <<"\n";
        for(int i=r+1;i<=res[j].first.second; i++)
        {
            cnt[a[i]]++;
            if (cnt[a[i]]==3) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=max(r,res[j].first.second);
//        cout << ans << "\n";
        for (int i=l; i<res[j].first.first; i++)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        l=max(l,res[j].first.first);
//        cout << ans << "\n";
        for (int i=r; i>res[j].first.second; i--)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=min(r,res[j].first.second);
//        cout << ans << "\n";
        dp[res[j].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 0 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 612 KB Output is correct
5 Correct 2441 ms 3984 KB Output is correct
6 Correct 2337 ms 4036 KB Output is correct
7 Execution timed out 5049 ms 7340 KB Time limit exceeded
8 Execution timed out 5052 ms 13036 KB Time limit exceeded
9 Execution timed out 5059 ms 14372 KB Time limit exceeded
10 Execution timed out 5050 ms 17332 KB Time limit exceeded