oj.uz

Submission #818212

# Submission time Handle Problem Language Result Execution time Memory
818212 2023-08-10T04:04:13 Z vjudge1 Poklon (COCI17_poklon) C++17
140 / 140
 341 ms 44588 KB 
#include <bits/stdc++.h>

using namespace std;
#define N 1000007
int n,q,l,r,cnt[N],a[N],ans[N],pre[3][N];
vector<pair<int,int>> b;
vector<pair<int,int>> res[N];
struct BIT {
	int size;
	vector<int> bit;
	BIT(int n) : size(n), bit(n + 1) {}
	void update(int x, int v) {
		for (; x <= size; x += x & (-x)) { bit[x] += v; }
	}
	/** @return sum of the values in [0,b] */
	int query(int b) {
		int result = 0;
		for (; b > 0; b -= b & (-b)) { result += bit[b]; }
		return result;
	}
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    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;
    BIT  bit(n);
    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=0; i<q; i++)
    {
        cin >> l >> r;
        l,r;
        res[r].push_back({l,i});
    }
    for(int i=1; i<=n; i++)
    {
        if (pre[1][a[i]]!=0) bit.update(pre[1][a[i]],-2);
        if(pre[0][a[i]]!=0) bit.update(pre[0][a[i]],1);
        if(pre[2][a[i]]!=0) bit.update(pre[2][a[i]],1);
//        cout << pre[1][a[i]] << " " << pre[0][a[i]] << " " << a[i] << "\n";
        long long s=bit.query(i);
//        cout << s << "\n";
        for (auto c:res[i])
        {
            ans[c.second]=s-bit.query(c.first-1);
        }
        pre[2][a[i]]=pre[1][a[i]];
        pre[1][a[i]]=pre[0][a[i]];
        pre[0][a[i]]=i;
    }
//    cout << "\n";
    for (int i=0; i<q; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:46:9: warning: left operand of comma operator has no effect [-Wunused-value]
   46 |         l,r;
      |         ^
poklon.cpp:46:12: warning: right operand of comma operator has no effect [-Wunused-value]
   46 |         l,r;
      |            ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23840 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23856 KB Output is correct
4 Correct 14 ms 24020 KB Output is correct
5 Correct 58 ms 27972 KB Output is correct
6 Correct 58 ms 27944 KB Output is correct
7 Correct 126 ms 32052 KB Output is correct
8 Correct 172 ms 36304 KB Output is correct
9 Correct 247 ms 40408 KB Output is correct
10 Correct 341 ms 44588 KB Output is correct