#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e6 + 1;
vector <vector <int> > vec(NMAX);
vector <int> t(4 * NMAX);
int curind[NMAX];
void update(int v, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r){
t[v] += val;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v] = t[2 * v] + t[2 * v + 1];
}
int get(int v, int l, int r, int st, int fin){
if(l > fin || r < st) return 0;
if(l >= st && r <= fin) return t[v];
int m = (l + r) / 2;
return get(2 * v, l, m, st, fin) + get(2 * v + 1, m + 1, r, st, fin);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
int q; cin >> q;
int a[n + 1];
map <int,int>mp;
int b[n + 1];
for(int i= 1; i <= n; i++){
cin >> a[i];
b[i] = a[i];
}
sort( b + 1, b + 1 + n);
for(int i = 1; i <= n; i++){
mp[b[i]] = i;
}
for(int i = 1; i <= n; i++) a[i] = mp[a[i]];
for(int i = 1; i <= n; i++){
vec[a[i]].pb(i);
curind[a[i]] = 2;
}
vector <vector <pii> > qv(n + 1);
vector <int> res(q + 1);
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
qv[l].pb({r, i});
}
for(int i = 1; i <= n; i++){
curind[i] = 2;
if(vec[i].size() < 2) {
continue;
}
else{
update(1, 1, n, vec[i][1], 1);
}
if(vec[i].size() >= 3) update(1, 1, n, vec[i][2], -1);
}
for(int l = 1; l <= n; l++){
for(auto to : qv[l]){
int r = to.f;
int ans = get(1, 1, n, l, r);
res[to.s] = ans;
}
if(curind[a[l]] > vec[a[l]].size()) continue;
int ind = vec[a[l]][curind[a[l]] - 1];
update(1, 1, n, ind, -1);
if(curind[a[l]] == vec[a[l]].size()) continue;
ind = vec[a[l]][curind[a[l]]];
if(curind[a[l]] < vec[a[l]].size())update(1, 1, n, ind, 2);
curind[a[l]]++;
if(curind[a[l]] < vec[a[l]].size()) ind = vec[a[l]][curind[a[l]]], update(1, 1, n, ind, -1);
}
for(int i = 1; i <= q; i++) cout << res[i] << "\n";
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(curind[a[l]] > vec[a[l]].size()) continue;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
poklon.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if(curind[a[l]] == vec[a[l]].size()) continue;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
poklon.cpp:83:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if(curind[a[l]] < vec[a[l]].size())update(1, 1, n, ind, 2);
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
poklon.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if(curind[a[l]] < vec[a[l]].size()) ind = vec[a[l]][curind[a[l]]], update(1, 1, n, ind, -1);
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
19 ms |
39508 KB |
Output is correct |
| 3 |
Correct |
22 ms |
39512 KB |
Output is correct |
| 4 |
Correct |
25 ms |
39764 KB |
Output is correct |
| 5 |
Correct |
147 ms |
45920 KB |
Output is correct |
| 6 |
Correct |
155 ms |
46032 KB |
Output is correct |
| 7 |
Correct |
338 ms |
52600 KB |
Output is correct |
| 8 |
Correct |
517 ms |
59768 KB |
Output is correct |
| 9 |
Correct |
699 ms |
66288 KB |
Output is correct |
| 10 |
Correct |
870 ms |
72444 KB |
Output is correct |
