/****************************************
* author: _anhtun.hi_ (ig,tiktok,cf,..) *
* mail:[email protected] *
****************************************/
#pragma GCC optimize("O2")
#pragma GCC target("sse4.2")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(h) h.begin(), h.end()
#define Log2(x) (63 - __builtin_clzll(x))
#define Forv(v, h) for(auto &v : h)
#define Rep(i, n) for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)
#define Time_run_code (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using ii = pair<int, int>;
using ull = unsigned long long;
using db = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<ii>;
const int MAXN = 5e5 + 5;
const int base = 5e5 + 1;
const int MOD = 5e5 + 9;
template <class X, class Y> bool maximize(X &a, const Y &b) {
if(a < b) return a = b, true;
return false;
}
template <class X, class Y> bool minimize(X &a, const Y &b) {
if(a > b) return a = b, true;
return false;
}
int n, Q, a[MAXN], Block;
int res[MAXN], cnt[MAXN];
struct Queries{
int l, r, id;
};
vector <Queries> H;
void input() {};
void process() {
int ans = 0;
cin >> n >> Q;
string num;
For(i, 1, n) {
int hash = 0;
cin >> num;
Forv(v, num) hash = ((hash << 1) + (hash << 3) + v - '0' + 1) % MOD;
a[i] = hash;
++cnt[a[i]];
if (cnt[a[i]] == 2) ++ans;
if (cnt[a[i]] == 3) --ans;
}
int u, v;
For(i, 1, Q) cin >> u >> v, H.emplace_back(Queries{u, v, i});
Block = sqrt(n);
sort(all(H), [&](const Queries &x, const Queries &y){
if (x.l / Block == y.l / Block) return x.r < y.r;
return x.l / Block < y.l / Block;
});
function<void(int)> add = [&](int val) {
++cnt[val];
if (cnt[val] == 2) ++ans;
if (cnt[val] == 3) --ans;
};
function<void(int)> remov = [&](int val) {
--cnt[val];
if (cnt[val] == 2) ++ans;
if (cnt[val] == 1) --ans;
};
// solve
int l = 1, r = n;
Forv(tmp, H) {
while (l < tmp.l) remov(a[l++]);
while (l > tmp.l) add(a[--l]);
while (r > tmp.r) remov(a[r--]);
while (r < tmp.r) add(a[++r]);
res[tmp.id] = ans;
}
For(i, 1, Q) cout << res[i] << '\n';
};
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//_______________________________
file("Poklon");
input();
process();
cerr << "Time elapsed: " << Time_run_code << " s.\n";
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:27:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:106:5: note: in expansion of macro 'file'
106 | file("Poklon");
| ^~~~
poklon.cpp:27:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:106:5: note: in expansion of macro 'file'
106 | file("Poklon");
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
4 ms |
592 KB |
Output is correct |
| 5 |
Correct |
150 ms |
4104 KB |
Output is correct |
| 6 |
Correct |
154 ms |
4032 KB |
Output is correct |
| 7 |
Correct |
435 ms |
8048 KB |
Output is correct |
| 8 |
Correct |
787 ms |
12480 KB |
Output is correct |
| 9 |
Correct |
1181 ms |
15968 KB |
Output is correct |
| 10 |
Correct |
1578 ms |
19912 KB |
Output is correct |
