oj.uz

Submission #21836

# Submission time Handle Problem Language Result Execution time Memory
21836 2017-04-26T09:49:27 Z mohammad_kilani Boat (APIO16_boat) C++14
0 / 100
 2000 ms 227140 KB 
#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);
        }
    }
    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){
                sum[j] = 1;
                continue;
            }
            sum[j] += getsum(0,all-1,1,0,idx[j]-1) + 1;
            if(sum[j] >= Mod)
                sum[j]-=Mod;
        }
        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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 21568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 21568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 227140 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 21568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -