oj.uz

Submission #716703

# Submission time Handle Problem Language Result Execution time Memory
716703 2023-03-30T21:27:01 Z snpmrnhlol Boat (APIO16_boat) C++17
9 / 100
 2000 ms 1156 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int segs[250000],dp[250000];
int length[1001];
int segl[1001];
int l[500],r[500];
int dp2[1001],dp3[1001],dp4[1001];;
int inv[250000];
int p(int a,int b){
    int r = 1;
    while(b > 0){
        if(b%2 == 1)r = 1ll*r*a%mod;
        a = 1ll*a*a%mod;
        b/=2;
    }
    return r;
}
void precalc(){
    for(int i = 0;i <= 250000;i++){
        inv[i] = p(i,mod - 2);
    }
}
int main(){
    int n,i,cnt = 1,j,cnt2 = 0,ans = 0;
    cin>>n;
    for(i = 0;i < n;i++){
        cin>>l[i]>>r[i];
        segl[i*2] = l[i];
        segl[i*2+1] = r[i] + 1;
    }
    sort(segl,segl + 2*n);
    for(i = 1;i < 2*n;i++){
        if(segl[i] != segl[cnt - 1]){
            segl[cnt++] = segl[i];
        }
    }
    for(i = 0;i < n;i++){
        for(j = cnt - 1;j >= 0;j--){
            if(l[i] <= segl[j] && segl[j] <= r[i]){
                segs[cnt2++] = j;
                length[j] = segl[j + 1] - segl[j];
            }
        }
    }
    segs[cnt2++] = cnt;
    length[cnt] = 1;
    for(i = 0;i < cnt2;i++){
        for(j = 0;j < 1001;j++){
            dp2[j] = length[j];
            dp3[j] = length[j];
            dp4[j] = 1;
        }
        dp[i] = 1;
        for(j = i - 1;j >= 0;j--){
            if(segs[j] < segs[i]){
                dp[i] = (dp[i] + 1ll*dp[j]*dp2[segs[j]])%mod;
                dp3[segs[j]] = 1ll*dp3[segs[j]]*(length[segs[j]] - dp4[segs[j]])%mod*inv[dp4[segs[j]] + 1]%mod;
                dp4[segs[j]]++;
                if(dp4[segs[j]] > length[segs[j]])dp2[segs[j]]+=dp3[segs[j]];
                dp2[segs[j]]%=mod;
            }
        }
    }
    ans = dp[cnt2 - 1] - 1;
    cout<<ans;
    return 0;
}

Compilation message

boat.cpp: In function 'void precalc()':
boat.cpp:21:16: warning: iteration 250000 invokes undefined behavior [-Waggressive-loop-optimizations]
   21 |         inv[i] = p(i,mod - 2);
      |         ~~~~~~~^~~~~~~~~~~~~~
boat.cpp:20:21: note: within this loop
   20 |     for(int i = 0;i <= 250000;i++){
      |                   ~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 320 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 320 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 316 KB Output is correct
10 Correct 3 ms 360 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 320 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 320 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 320 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 316 KB Output is correct
10 Correct 3 ms 360 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 320 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Execution timed out 2056 ms 1156 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 320 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 320 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 316 KB Output is correct
10 Correct 3 ms 360 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 320 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Execution timed out 2056 ms 1156 KB Time limit exceeded
22 Halted 0 ms 0 KB -