| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 409869 |
2021-05-21T17:37:25 Z |
LptN21 |
Poklon (COCI17_poklon) |
C++14 |
|
1264 ms |
45124 KB |
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
const int N = 5e5+7, M=1e2+1;
const int MOD = 1e9+7;
int n, m, k, t;
struct Node{int v;} st[N<<2];
void update(int idx, int l0, int r0, int l, int r, int v) {
if(l0>r||r0<l) return;
if(l<=l0&&r0<=r) {st[idx].v+=v;return;}
int mid=(l0+r0)/2;
update(idx*2, l0, mid, l, r, v), update(idx*2+1, mid+1, r0, l, r, v);
st[idx].v=st[idx*2].v+st[idx*2+1].v;
}
int query(int idx, int l0, int r0, int l, int r) {
if(l0>r||r0<l) return 0;
if(l<=l0&&r0<=r) return st[idx].v;
int mid=(l0+r0)/2;
return query(idx*2, l0, mid, l, r)+query(idx*2+1, mid+1, r0, l, r);
}
void upd(int l, int r, int v) {update(1, 1, n, l, r, v);}
int qry(int l, int r) {return query(1, 1, n, l, r);}
map<int, int> cnt;
map<int, vector<int> > lst;
int ans[N], a[N];
vector<ii> q[N];
signed main() {
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//fastIO;
scanf("%d%d", &n, &m);int l, r;
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
for(int i=1;i<=m;i++) {
scanf("%d%d", &l, &r);
q[r].pb(ii(i, l));
}
for(int i=1;i<=n;i++) {
cnt[a[i]]++;
if(cnt[a[i]]>1) {
int vsz=sz(lst[a[i]]);
if(vsz==1) upd(1, lst[a[i]][vsz-1], 1);
else {
if(vsz==2) t=1;
else t=lst[a[i]][vsz-3]+1;
upd(t, lst[a[i]][vsz-2], -2);
upd(lst[a[i]][vsz-2]+1, lst[a[i]][vsz-1], 1);
}
}
for(int j=0;j<sz(q[i]);j++) {
k=q[i][j].SS, t=q[i][j].FF;
ans[t]=qry(k, i);
}
lst[a[i]].pb(i);
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}
/* stuff you should look for
- int overflow, array bounds
- special cases (n=1?)
- do smth instead of do nothing and stay organized
- WRITE STUFF DOWN
- DONT JUST STICK ON ONE APPROACH
*/
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d", &n, &m);int l, r;
| ~~~~~^~~~~~~~~~~~~~~~
poklon.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | for(int i=1;i<=n;i++) scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
poklon.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12064 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
11976 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
12108 KB |
Output isn't correct |
| 4 |
Incorrect |
14 ms |
12400 KB |
Output isn't correct |
| 5 |
Incorrect |
186 ms |
18488 KB |
Output isn't correct |
| 6 |
Incorrect |
193 ms |
18504 KB |
Output isn't correct |
| 7 |
Incorrect |
464 ms |
25624 KB |
Output isn't correct |
| 8 |
Incorrect |
773 ms |
34124 KB |
Output isn't correct |
| 9 |
Incorrect |
986 ms |
39816 KB |
Output isn't correct |
| 10 |
Incorrect |
1264 ms |
45124 KB |
Output isn't correct |
