oj.uz

Submission #893385

# Submission time Handle Problem Language Result Execution time Memory
893385 2023-12-27T03:56:46 Z Warinchai Pilot (NOI19_pilot) C++14
28 / 100
 33 ms 35888 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
int ar[1000005];
int asum[1000005];
int ssum[1000005];
int rsum[1000005];
vector<int>v;
struct node{
    int val;
    int sz;
    node *l;
    node *r;
    node(int x=0){
        val=x;
        l=NULL;
        r=NULL;
        sz=0;
    }
};
node *rt=NULL;
vector<int>qr;
stack<node*>s;
void dfs(node *u){
    u->sz=1;
    if(u->l){
        dfs(u->l);
        u->sz+=u->l->sz;
    }
    if(u->r){
        dfs(u->r);
        u->sz+=u->r->sz;
    }
    //cerr<<u->val<<" "<<u->sz<<"\n";
}
void dfs2(node *u,int pn=0){
    asum[u->val]+=(u->sz)*((u->sz)+1)/2;
    ssum[pn-1]+=(u->sz)*((u->sz)+1)/2;
    if(u->l)dfs2(u->l,u->val);
    if(u->r)dfs2(u->r,u->val);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    for(int i=0;i<q;i++){
        int a;cin>>a;
        qr.push_back(a);
    }
    //sort(qr.begin(),qr.end(),greater<pair<int,int> >());
    for(int i=1;i<=n;i++){
        int x=ar[i];
        node *p=NULL;
        while(!s.empty()&&s.top()->val<x){
            p=s.top();
            s.pop();
        }
        if(s.empty()){
            rt=new node(x);
            rt->l=p;
            s.push(rt);
        }else{
            s.top()->r=new node(x);
            s.top()->r->l=p;
            s.push(s.top()->r);
        }
    }
    dfs(rt);
    dfs2(rt,1e6+2);
    long long sum=0;
    for(int i=1;i<=1e6;i++){
        sum+=asum[i];
        rsum[i]=sum;
        sum-=ssum[i];
    }
    for(auto x:qr)cout<<rsum[x]<<"\n";
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20056 KB Output is correct
2 Correct 21 ms 30548 KB Output is correct
3 Correct 16 ms 19804 KB Output is correct
4 Correct 16 ms 30044 KB Output is correct
5 Correct 14 ms 19812 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25048 KB Output is correct
2 Correct 27 ms 25160 KB Output is correct
3 Correct 26 ms 25016 KB Output is correct
4 Correct 27 ms 25296 KB Output is correct
5 Correct 27 ms 24792 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 35588 KB Output is correct
2 Correct 30 ms 35380 KB Output is correct
3 Correct 33 ms 35280 KB Output is correct
4 Correct 31 ms 35888 KB Output is correct
5 Correct 31 ms 35536 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 4 ms 18524 KB Output is correct
3 Correct 3 ms 16476 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 16308 KB Output is correct
6 Incorrect 3 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -