oj.uz

Submission #486373

# Submission time Handle Problem Language Result Execution time Memory
486373 2021-11-11T13:11:49 Z leinad2 역사적 조사 (JOI14_historical) C++17
0 / 100
 7 ms 588 KB 
#include<bits/stdc++.h>
using namespace std;
int n, q, i, j, k, a, b, B, inv[100010], A[100010], cnt[100010];
vector<int>comp;
long long ans[100010], seg[400010];
struct query
{
    int i, l, r;
};
vector<query>Q;
bool cmp(query a, query b)
{
    if(a.l/B==b.l/B)return a.r<b.r;
    else return a.l/B<b.l/B;
}
void update(int id, int s, int e, int x, int v)
{
    if(e<x||x<s)return;
    if(s==e)
    {
        seg[id]=v;
        return;
    }
    int m=s+e>>1;
    update(id*2, s, m, x, v);update(id*2+1, m+1, e, x, v);
    seg[id]=max(seg[id*2], seg[id*2+1]);
}
void add(int i)
{
    cnt[A[i]]++;
    update(1, 1, n, A[i], 1LL*cnt[A[i]]*inv[A[i]]);
}
void del(int i)
{
    cnt[A[i]]--;
    update(1, 1, n, A[i], 1LL*cnt[A[i]]*inv[A[i]]);
}
main()
{
    for(scanf("%d %d", &n, &q);i++<n;)
    {
        scanf("%d", &A[i]);
        comp.push_back(A[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for(i=0;i++<n;)
    {
        a=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
        inv[a]=A[i];
        A[i]=a;
    }
    B=(int)sqrt(n);
    for(i=0;i++<q;)
    {
        scanf("%d %d", &a, &b);
        Q.push_back({i, a, b});
    }
    sort(Q.begin(), Q.end(), cmp);
    for(i=Q[0].l;i<=Q[0].r;i++)add(i);
    ans[Q[0].i]=seg[1];
    for(i=1;i<q;i++)
    {
        if(Q[i].l<Q[i-1].l)for(j=Q[i-1].l-1;j>=Q[i].l;j--)add(j);
        else for(j=Q[i-1].l;j<Q[i].l;j++)del(j);
        if(Q[i].r>Q[i-1].r)for(j=Q[i-1].r+1;j<=Q[i].r;j++)add(j);
        else for(j=Q[i-1].r;j>Q[i].r;j--)del(j);
        ans[Q[i].i]=seg[1];
    }
    for(i=0;i++<q;)printf("%lld\n", ans[i]);
}

Compilation message

historic.cpp: In function 'void update(int, int, int, int, int)':
historic.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int m=s+e>>1;
      |           ~^~
historic.cpp: At global scope:
historic.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main()
      | ^~~~
historic.cpp: In function 'int main()':
historic.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(scanf("%d %d", &n, &q);i++<n;)
      |         ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
historic.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Incorrect 7 ms 588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -