Submission #239806

#	Time	Username	Problem	Language	Result	Execution time	Memory
239806		mhy908	Pilot (NOI19_pilot)	C++14	89 / 100	1098 ms	125304 KiB

pilot

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
#define ub(x, v) upper_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2000000000000000000;
const LL mod1=1000000007;
const LL mod2=998244353;
const int inf=2000000000;
int n, q;
vector<int> vc[1000010];
LL ans[1000010];
struct SEGMENT_TREE{
    struct NODE{
        LL l, r, ans, len;
    }tree[4000010];
    NODE f(NODE a, NODE b){
        NODE ret={0, 0, 0, 0};
        ret.len=a.len+b.len;
        ret.ans=a.ans+b.ans+a.r*b.l;
        if(a.len==a.l)ret.l=a.l+b.l;
        else ret.l=a.l;
        if(b.len==b.r)ret.r=b.r+a.r;
        else ret.r=b.r;
        return ret;
    }
    void init(int point, int s, int e){
        if(s==e){
            tree[point]={0, 0, 0, 1};
            return;
        }
        init(point*2, s, (s+e)/2);
        init(point*2+1, (s+e)/2+1, e);
        tree[point]=f(tree[point*2], tree[point*2+1]);
    }
    void update(int point, int s, int e, int num){
        if(s==e){
            tree[point]={1, 1, 1, 1};
            return;
        }
        if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num);
        else update(point*2+1, (s+e)/2+1, e, num);
        tree[point]=f(tree[point*2], tree[point*2+1]);
    }
    LL query(){return tree[1].ans;}
}seg;
int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        int a;
        scanf("%d", &a);
        vc[a].eb(i);
    }
    seg.init(1, 1, n);
    for(int i=1; i<=1000000; i++){
        for(auto j:vc[i])seg.update(1, 1, n, j);
        ans[i]=seg.query();
    }
    for(int i=1; i<=q; i++){
        int a;
        scanf("%d", &a);
        printf("%lld\n", ans[a]);
    }
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
pilot.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
pilot.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11