답안 #21840 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
21840	2017-04-26T10:06:41 Z	mohammad_kilani	Boat (APIO16_boat)	C++14	31 / 100	1279 ms	118268 KB

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

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

#	결과	메모리	Grader output
1	Correct	25472 KB	Output is correct
2	Correct	25472 KB	Output is correct
3	Correct	25472 KB	Output is correct
4	Correct	25472 KB	Output is correct
5	Correct	25472 KB	Output is correct
6	Correct	25472 KB	Output is correct
7	Correct	25472 KB	Output is correct
8	Correct	25472 KB	Output is correct
9	Correct	25472 KB	Output is correct
10	Correct	25472 KB	Output is correct
11	Correct	25472 KB	Output is correct
12	Correct	25472 KB	Output is correct
13	Correct	25472 KB	Output is correct
14	Correct	25472 KB	Output is correct
15	Correct	25472 KB	Output is correct
16	Correct	25472 KB	Output is correct
17	Correct	25472 KB	Output is correct
18	Correct	25472 KB	Output is correct
19	Correct	25472 KB	Output is correct
20	Correct	25472 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	25472 KB	Output is correct
2	Correct	0 ms	25472 KB	Output is correct
3	Correct	0 ms	25472 KB	Output is correct
4	Correct	0 ms	25472 KB	Output is correct
5	Correct	0 ms	25472 KB	Output is correct
6	Correct	0 ms	25472 KB	Output is correct
7	Correct	0 ms	25472 KB	Output is correct
8	Correct	0 ms	25472 KB	Output is correct
9	Correct	0 ms	25472 KB	Output is correct
10	Correct	0 ms	25472 KB	Output is correct
11	Correct	0 ms	25472 KB	Output is correct
12	Correct	0 ms	25472 KB	Output is correct
13	Correct	0 ms	25472 KB	Output is correct
14	Correct	0 ms	25472 KB	Output is correct
15	Correct	0 ms	25472 KB	Output is correct
16	Correct	0 ms	25472 KB	Output is correct
17	Correct	0 ms	25472 KB	Output is correct
18	Correct	0 ms	25472 KB	Output is correct
19	Correct	0 ms	25472 KB	Output is correct
20	Correct	0 ms	25472 KB	Output is correct
21	Correct	333 ms	26000 KB	Output is correct
22	Correct	346 ms	26000 KB	Output is correct
23	Correct	329 ms	26000 KB	Output is correct
24	Correct	363 ms	26000 KB	Output is correct
25	Correct	363 ms	26000 KB	Output is correct
26	Correct	369 ms	25868 KB	Output is correct
27	Correct	369 ms	25868 KB	Output is correct
28	Correct	369 ms	25868 KB	Output is correct
29	Correct	379 ms	25868 KB	Output is correct
30	Correct	1253 ms	118136 KB	Output is correct
31	Correct	1279 ms	116552 KB	Output is correct
32	Correct	1246 ms	118268 KB	Output is correct
33	Correct	1183 ms	115760 KB	Output is correct
34	Correct	1226 ms	116684 KB	Output is correct
35	Correct	1012 ms	112460 KB	Output is correct
36	Correct	1059 ms	115496 KB	Output is correct
37	Correct	1073 ms	116552 KB	Output is correct
38	Correct	1053 ms	113516 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	553 ms	72332 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	25472 KB	Output is correct
2	Correct	0 ms	25472 KB	Output is correct
3	Correct	0 ms	25472 KB	Output is correct
4	Correct	0 ms	25472 KB	Output is correct
5	Correct	0 ms	25472 KB	Output is correct
6	Correct	0 ms	25472 KB	Output is correct
7	Correct	0 ms	25472 KB	Output is correct
8	Correct	0 ms	25472 KB	Output is correct
9	Correct	0 ms	25472 KB	Output is correct
10	Correct	0 ms	25472 KB	Output is correct
11	Correct	0 ms	25472 KB	Output is correct
12	Correct	0 ms	25472 KB	Output is correct
13	Correct	0 ms	25472 KB	Output is correct
14	Correct	0 ms	25472 KB	Output is correct
15	Correct	0 ms	25472 KB	Output is correct
16	Correct	0 ms	25472 KB	Output is correct
17	Correct	0 ms	25472 KB	Output is correct
18	Correct	0 ms	25472 KB	Output is correct
19	Correct	0 ms	25472 KB	Output is correct
20	Correct	0 ms	25472 KB	Output is correct
21	Correct	333 ms	26000 KB	Output is correct
22	Correct	346 ms	26000 KB	Output is correct
23	Correct	329 ms	26000 KB	Output is correct
24	Correct	363 ms	26000 KB	Output is correct
25	Correct	363 ms	26000 KB	Output is correct
26	Correct	369 ms	25868 KB	Output is correct
27	Correct	369 ms	25868 KB	Output is correct
28	Correct	369 ms	25868 KB	Output is correct
29	Correct	379 ms	25868 KB	Output is correct
30	Correct	1253 ms	118136 KB	Output is correct
31	Correct	1279 ms	116552 KB	Output is correct
32	Correct	1246 ms	118268 KB	Output is correct
33	Correct	1183 ms	115760 KB	Output is correct
34	Correct	1226 ms	116684 KB	Output is correct
35	Correct	1012 ms	112460 KB	Output is correct
36	Correct	1059 ms	115496 KB	Output is correct
37	Correct	1073 ms	116552 KB	Output is correct
38	Correct	1053 ms	113516 KB	Output is correct
39	Runtime error	553 ms	72332 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

답안 #21840

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0