Submission #21837

#	Time	Username	Problem	Language	Result	Execution time	Memory
21837		mohammad_kilani	Boat (APIO16_boat)	C++14	0 / 100	2000 ms	233740 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define Mod 1000000007

int n;
int l[1000];
int r[1000];
int sum[1000010];
int seg[4000010];
map<int,bool> taken;
map<int,int> idx;
vector<int> v;


int getsum(int s,int e,int idx,int l,int r){
    if(s > r || e < l)
        return 0;
    if(s >=l && e <= r)
        return seg[idx];
    int f = getsum(s,(s+e)/2,idx*2,l,r);
    if(f >= Mod)
        f-=Mod;
    int ss = getsum((s+e)/2+1,e,idx*2+1,l,r);
    if(ss >= Mod)
        ss-=Mod;
    f+=ss;
    if(f >= Mod)
        f-=Mod;
    return f;
}

int update(int s,int e,int idx,int idx2,int val){
    if(s > idx2 || e < idx2)
        return seg[idx];
    if(s == idx2 && e == idx2)
        return seg[idx] = val;
    int f = update(s,(s+e)/2,idx*2,idx2,val);
    if(f >= Mod)
        f-=Mod;
    int ss = update((s+e)/2+1,e,idx*2+1,idx2,val);
    if(ss >= Mod)
        ss-=Mod;
    seg[idx] = f+ ss;
    if(seg[idx] >= Mod)
        seg[idx]-=Mod;
    return seg[idx];
}


int main() {
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    int all = 0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&l[i],&r[i]);
        for(int j=l[i];j<=r[i];j++){
            if(taken[j])
                continue;
            taken[j] = true;
            v.push_back(j);
        }
    }
    int ans = 0 ;
    all = v.size();
    sort(v.begin(),v.end());
    for(int i=0;i<(int)v.size();i++){
        idx[v[i]] = i ;
    }
    for(int i=0;i<n;i++){
        for(int j=l[i];j<=r[i];j++){
            if(idx[j] == 0){
                ans++;
                if(ans >= Mod)
                    ans-=Mod;
                sum[j]++;
                if(sum[j] >= Mod)
                    sum[j]-=Mod;
                continue;
            }
            int cur = 0;
            cur = getsum(0,all-1,1,0,idx[j]-1) + 1;
            if(cur >= Mod)
                cur-=Mod;
            ans+=cur;
            sum[j]+=cur;
        }
        for(int j=l[i];j<=r[i];j++){
            update(0,all-1,1,idx[j],sum[j]);
        }
    }
    printf("%d\n",getsum(0,all-1,1,0,all-1));
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:52:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
boat.cpp:55:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&l[i],&r[i]);
                                  ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42