oj.uz

Submission #818069

# Submission time Handle Problem Language Result Execution time Memory
818069 2023-08-10T01:28:01 Z vjudge1 Poklon (COCI17_poklon) C++17
0 / 140
 5000 ms 17088 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)
    {
        for(int i=r+1;i<=c.first.second; i++)
        {
            cnt[a[i]]++;
            if (cnt[a[i]]>2) ans--;
            if(cnt[a[i]]==2) ans++;
        }
        r=max(r,c.first.second);
        for (int i=l; i<c.first.first; i++)
        {
            cnt[a[i]]--;
            if(cnt[a[i]]==1) ans--;
            if(cnt[a[i]]==2) ans++;
        }
//        cout << ans << "\n";
        l=max(l,c.first.first);
        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);
        dp[c.second]=ans;
    }
    for(int i=1; i<=q; i++) cout << dp[i] << "\n";
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 9 ms 596 KB Output isn't correct
5 Incorrect 1998 ms 4888 KB Output isn't correct
6 Incorrect 1991 ms 4880 KB Output isn't correct
7 Execution timed out 5080 ms 7308 KB Time limit exceeded
8 Execution timed out 5065 ms 13052 KB Time limit exceeded
9 Execution timed out 5074 ms 14372 KB Time limit exceeded
10 Execution timed out 5077 ms 17088 KB Time limit exceeded