Submission #38808

#	Time	Username	Problem	Language	Result	Execution time	Memory
38808		Waschbar	Boat (APIO16_boat)	C++14	31 / 100	1463 ms	118264 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;
int v[1000010];
int last = 0 ;
 
 
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);
    int ss = getsum((s+e)/2+1,e,idx*2+1,l,r);
    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);
    int ss = update((s+e)/2+1,e,idx*2+1,idx2,val);
    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[last] = j;
            last++;
        }
    }
    int ans = 0 ;
    all = last;
    sort(v,v+all);
    for(int i=0;i<all;i++){
        idx[v[i]] = i ;
    }
    for(int i=0;i<n;i++){
            int id = idx[l[i]];
            int idd;
        for(int j=l[i];j<=r[i];j++){
                idd = id+j-l[i];
            if(idd == 0){
                ans++;
                if(ans >= Mod)
                    ans-=Mod;
                sum[0]++;
                if(sum[0] >= Mod)
                    sum[0]-=Mod;
                continue;
            }
            int cur = 0;
            cur = getsum(0,all-1,1,0,idd-1) + 1;
            if(cur >= Mod)
                cur-=Mod;
            ans+=cur;
            if(ans >= Mod)
                ans-=Mod;
            sum[idd]+=cur;
                if(sum[idd] >= Mod)
                    sum[idd] -= Mod;
        }
        for(int j=l[i];j<=r[i];j++){
            update(0,all-1,1,id+j-l[i],sum[id+j-l[i]]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:45:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
boat.cpp:48: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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42