Submission #20465

#	Time	Username	Problem	Language	Result	Execution time	Memory
20465		jjwdi0	역사적 조사 (JOI14_historical)	C++11	100 / 100	2943 ms	12320 KiB

historic

#include <stdio.h>
#include <map>
#include <algorithm>
#define SQRT 320
using namespace std;
typedef long long ll;
struct query{
    int l, r, ti;
    ll ans;
}T[111111];
struct seg_tree{
    ll tree[1<<18];
    int base;
    void init(int x) {base=1; while(base<x) base<<=1;}
    void update(int x, ll y) {
        x += base - 1;
        while(x) {
            tree[x]=y;
            y=max(tree[x/2*2], tree[x/2*2+1]);
            if(y == tree[x/2]) return;
            x>>=1;
        }
    }
    ll RMQ(int s, int e) {
        s += base - 1, e += base - 1;
        ll res=0;
        while(s<e) {
            if(s&1) res=max(res, tree[s++]);
            if(!(e&1)) res=max(res, tree[e--]);
            s>>=1; e>>=1;
        }
        if(s == e) res = max(res, tree[e]);
        return res;
    }
};
seg_tree s;
bool cmp1(const query &x, const query &y){return x.l/SQRT == y.l/SQRT ? x.r < y.r : x.l < y.l;}
bool cmp2(const query &x, const query &y){return x.ti < y.ti;}
int N, Q, A[111111], cnt[111111];
ll B[111111];
map<int, int> m;
int main() {
    scanf("%d %d", &N, &Q);
    s.init(N);
    for(int i=1; i<=N; i++) {
        scanf("%d", &A[i]);
        if(m[A[i]]) B[i]=(ll)A[i], A[i]=m[A[i]];
        else m[A[i]]=i, B[i]=(ll)A[i], A[i]=i;
    }
    for(int i=0; i<Q; i++) scanf("%d %d", &T[i].l, &T[i].r), T[i].ti=i;
    sort(T, T+Q, cmp1);
    int l=1, r=0;
    for(int i=0; i<Q; i++) {
        if(r < T[i].r) {
            while(r != T[i].r) {
                cnt[A[++r]]++;
                s.update(A[r], B[r]*cnt[A[r]]);
            }
        }
        else {
            while(r != T[i].r) {
                cnt[A[r]]--;
                s.update(A[r], B[r]*cnt[A[r]]);
                r--;
            }
        }
        if(l > T[i].l) {
            while(l != T[i].l) {  
                cnt[A[--l]]++;
                s.update(A[l], B[l]*cnt[A[l]]);
            }
        }
        else {  
            while(l != T[i].l) {  
                cnt[A[l]]--;
                s.update(A[l], B[l]*cnt[A[l]]);
                l++;
            }
        }
        T[i].ans = s.RMQ(1, N);
    }  
    sort(T, T+Q, cmp2);
    for(int i=0; i<Q; i++) printf("%lld\n", T[i].ans);
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &Q);
                           ^
historic.cpp:46:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
                           ^
historic.cpp:50:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<Q; i++) scanf("%d %d", &T[i].l, &T[i].r), T[i].ti=i;
                                                                       ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60