oj.uz

Submission #400613

# Submission time Handle Problem Language Result Execution time Memory
400613 2021-05-08T12:01:56 Z Hazem Boat (APIO16_boat) C++14
0 / 100
 2000 ms 169284 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e5+10;
const int M = 5e3+10;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

LL add(LL a,LL b){
    return (a+b)%MOD;
}

struct node {

    node *lc,*rc;
    LL sum = 0,l,r;
    node():lc(NULL),rc(NULL),sum(0){};
};

void update(node * &v,int l,int r,int pos,LL val){

    if(v==NULL){
        v = new node();
        v->l = l;v->r = r;
    }

    if(l==r){
        v->sum = add(v->sum,val);
        return ;
    }

    int mid = (l+r)/2;
    if(pos<=mid)
        update(v->lc,l,mid,pos,val);
    else 
        update(v->rc,mid+1,r,pos,val);

    v->sum = (v->lc==NULL?0:v->lc->sum)+(v->rc==NULL?0:v->rc->sum);
}

LL get(node * &v,int l,int r,int tl,int tr){

    if(v==NULL){
        v = new node();
        v->l = l;v->r = r;
    }

    if(tl>=l&&tr<=r)
        return v->sum;

    if(tl>r||tr<l)
        return 0;

    int mid = (tl+tr)/2;
    return add(get(v->lc,l,r,tl,mid),get(v->rc,l,r,mid+1,tr));
}

node *root;

int main(){

    //freopen("out.txt","w",stdout);
    
    int n;
    scanf("%d",&n);

    update(root,0,INF,0,1);

    LL ans = 0;
    for(int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        for(int j=r;j>=l;j--){
            update(root,0,INF,j,get(root,0,j-1,0,INF));
            ans = add(ans,get(root,j,j,0,INF));
        }
    }

    printf("%lld\n",(ans-(n>1)+MOD)%MOD);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
boat.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 169284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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