답안 #38808 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38808	2018-01-06T16:02:21 Z	Waschbar	Boat (APIO16_boat)	C++14	31 / 100	1463 ms	118264 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	25468 KB	Output is correct
2	Correct	25468 KB	Output is correct
3	Correct	25468 KB	Output is correct
4	Correct	25468 KB	Output is correct
5	Correct	25468 KB	Output is correct
6	Correct	25468 KB	Output is correct
7	Correct	25468 KB	Output is correct
8	Correct	25468 KB	Output is correct
9	Correct	25468 KB	Output is correct
10	Correct	25468 KB	Output is correct
11	Correct	25468 KB	Output is correct
12	Correct	25468 KB	Output is correct
13	Correct	25468 KB	Output is correct
14	Correct	25468 KB	Output is correct
15	Correct	25468 KB	Output is correct
16	Correct	25468 KB	Output is correct
17	Correct	25468 KB	Output is correct
18	Correct	25468 KB	Output is correct
19	Correct	25468 KB	Output is correct
20	Correct	25468 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	25468 KB	Output is correct
2	Correct	0 ms	25468 KB	Output is correct
3	Correct	0 ms	25468 KB	Output is correct
4	Correct	0 ms	25468 KB	Output is correct
5	Correct	0 ms	25468 KB	Output is correct
6	Correct	0 ms	25468 KB	Output is correct
7	Correct	0 ms	25468 KB	Output is correct
8	Correct	0 ms	25468 KB	Output is correct
9	Correct	0 ms	25468 KB	Output is correct
10	Correct	0 ms	25468 KB	Output is correct
11	Correct	0 ms	25468 KB	Output is correct
12	Correct	0 ms	25468 KB	Output is correct
13	Correct	0 ms	25468 KB	Output is correct
14	Correct	0 ms	25468 KB	Output is correct
15	Correct	0 ms	25468 KB	Output is correct
16	Correct	0 ms	25468 KB	Output is correct
17	Correct	0 ms	25468 KB	Output is correct
18	Correct	0 ms	25468 KB	Output is correct
19	Correct	0 ms	25468 KB	Output is correct
20	Correct	0 ms	25468 KB	Output is correct
21	Correct	376 ms	25996 KB	Output is correct
22	Correct	369 ms	25996 KB	Output is correct
23	Correct	339 ms	25996 KB	Output is correct
24	Correct	433 ms	25996 KB	Output is correct
25	Correct	423 ms	25996 KB	Output is correct
26	Correct	379 ms	25864 KB	Output is correct
27	Correct	399 ms	25864 KB	Output is correct
28	Correct	399 ms	25864 KB	Output is correct
29	Correct	416 ms	25864 KB	Output is correct
30	Correct	1409 ms	118132 KB	Output is correct
31	Correct	1463 ms	116548 KB	Output is correct
32	Correct	1429 ms	118264 KB	Output is correct
33	Correct	1349 ms	115756 KB	Output is correct
34	Correct	1439 ms	116680 KB	Output is correct
35	Correct	1109 ms	112456 KB	Output is correct
36	Correct	1243 ms	115492 KB	Output is correct
37	Correct	1266 ms	116548 KB	Output is correct
38	Correct	1169 ms	113512 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	563 ms	72328 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	25468 KB	Output is correct
2	Correct	0 ms	25468 KB	Output is correct
3	Correct	0 ms	25468 KB	Output is correct
4	Correct	0 ms	25468 KB	Output is correct
5	Correct	0 ms	25468 KB	Output is correct
6	Correct	0 ms	25468 KB	Output is correct
7	Correct	0 ms	25468 KB	Output is correct
8	Correct	0 ms	25468 KB	Output is correct
9	Correct	0 ms	25468 KB	Output is correct
10	Correct	0 ms	25468 KB	Output is correct
11	Correct	0 ms	25468 KB	Output is correct
12	Correct	0 ms	25468 KB	Output is correct
13	Correct	0 ms	25468 KB	Output is correct
14	Correct	0 ms	25468 KB	Output is correct
15	Correct	0 ms	25468 KB	Output is correct
16	Correct	0 ms	25468 KB	Output is correct
17	Correct	0 ms	25468 KB	Output is correct
18	Correct	0 ms	25468 KB	Output is correct
19	Correct	0 ms	25468 KB	Output is correct
20	Correct	0 ms	25468 KB	Output is correct
21	Correct	376 ms	25996 KB	Output is correct
22	Correct	369 ms	25996 KB	Output is correct
23	Correct	339 ms	25996 KB	Output is correct
24	Correct	433 ms	25996 KB	Output is correct
25	Correct	423 ms	25996 KB	Output is correct
26	Correct	379 ms	25864 KB	Output is correct
27	Correct	399 ms	25864 KB	Output is correct
28	Correct	399 ms	25864 KB	Output is correct
29	Correct	416 ms	25864 KB	Output is correct
30	Correct	1409 ms	118132 KB	Output is correct
31	Correct	1463 ms	116548 KB	Output is correct
32	Correct	1429 ms	118264 KB	Output is correct
33	Correct	1349 ms	115756 KB	Output is correct
34	Correct	1439 ms	116680 KB	Output is correct
35	Correct	1109 ms	112456 KB	Output is correct
36	Correct	1243 ms	115492 KB	Output is correct
37	Correct	1266 ms	116548 KB	Output is correct
38	Correct	1169 ms	113512 KB	Output is correct
39	Runtime error	563 ms	72328 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

답안 #38808

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