Submission #818207

#	Time	Username	Problem	Language	Result	Execution time	Memory
818207		vjudge1	Poklon (COCI17_poklon)	C++17	0 / 140	290 ms	47248 KiB

poklon

#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);
//        cout << pre[1][a[i]] << " " << pre[0][a[i]] << " " << a[i] << "\n";
//        pre[2][a[i]]=pre[1][a[i]];
        pre[1][a[i]]=pre[0][a[i]];
        pre[0][a[i]]=i;
        long long s=bit.query(i);
//        cout << s << "\n";
        for (auto c:res[i])
        {
            ans[c.second]=s-bit.query(c.first-1);
        }
    }
//    cout << "\n";
    for (int i=0; i<q; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

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: 0 / 140