Submission #400620

#	Time	Username	Problem	Language	Result	Execution time	Memory
400620		Hazem	Boat (APIO16_boat)	C++14	31 / 100	2099 ms	161364 KiB

boat

#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 = add((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,0,j-1,0,INF));
        }
    }

    printf("%lld\n",ans);
}   

Compilation message (stderr)

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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42