oj.uz

Submission #984140

# Submission time Handle Problem Language Result Execution time Memory
984140 2024-05-16T10:40:53 Z Aiperiii Boat (APIO16_boat) C++14
9 / 100
 2000 ms 15708 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mod=1e9+7;
int f(int n){
    return ((n*(n+1))/2)%mod;
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector <int> a(n+1),b(n+1);
    map <int,int> ed;
    set <int> v;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        v.insert(a[i]);
        v.insert(b[i]);
        ed[b[i]]++;
    }
    int p=-1,ls=-1;
    vector <pair <int,int> > r;
    for(auto x : v){
        ls=x;
        if(p!=-1 && x-1>=p)r.pb({p,x-1});
        if(ed[x]){
            r.pb({x,x});
            p=x+1;
        }
        else p=x;
    }
    if(p==ls)r.pb({p,p});
    //for(auto x : r)cout<<x.ff<<" "<<x.ss<<"\n";
    
    vector <vector <int> > val(n+1,vector <int> (r.size())),cnt(n+1,vector <int> (r.size())),add(n+1,vector <int> (r.size()));
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            if(a[i]<=r[j].ff && r[j].ss<=b[i]){
                cnt[i][j]=r[j].ss-r[j].ff+1;
                val[i][j]=1;
            }
            //cout<<cnt[i][j]<<" ";
        }
      //  cout<<"\n";
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            if(a[i]<=r[j].ff && r[j].ss<=b[i]){
                for(int k=1;k<i;k++){
                    for(int q=0;q<j;q++){
                        val[i][j]+=val[k][q]*cnt[k][q];
                        val[i][j]%=mod;
                        val[i][j]+=add[k][q];
                        val[i][j]%=mod;
                    }
                    if(cnt[i][j]){
                        add[i][j]+=val[k][j]*f(cnt[i][j]-1);
                        add[i][j]%=mod;
                    }
                }
            }
        }
    }
    int ans=0;
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<r.size();j++){
            ans+=val[i][j]*cnt[i][j];
            ans%=mod;
            ans+=add[i][j];
            ans%=mod;
            //cout<<val[i][j]<<" ";
        }
        //cout<<"\n";
    }
    cout<<ans<<"\n";
}
/*
 3
 1 10
 3 10
 8 15
 
2
1 2
2 3
*/

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:53:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:73:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12368 KB Output is correct
2 Correct 488 ms 12120 KB Output is correct
3 Correct 485 ms 12308 KB Output is correct
4 Correct 472 ms 12304 KB Output is correct
5 Correct 485 ms 12124 KB Output is correct
6 Correct 628 ms 12308 KB Output is correct
7 Correct 632 ms 12308 KB Output is correct
8 Correct 628 ms 12296 KB Output is correct
9 Correct 627 ms 12120 KB Output is correct
10 Correct 629 ms 12120 KB Output is correct
11 Correct 630 ms 12300 KB Output is correct
12 Correct 625 ms 12300 KB Output is correct
13 Correct 628 ms 12308 KB Output is correct
14 Correct 633 ms 12300 KB Output is correct
15 Correct 629 ms 12124 KB Output is correct
16 Correct 63 ms 2392 KB Output is correct
17 Correct 67 ms 2704 KB Output is correct
18 Correct 67 ms 2612 KB Output is correct
19 Correct 65 ms 2652 KB Output is correct
20 Correct 68 ms 2628 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12368 KB Output is correct
2 Correct 488 ms 12120 KB Output is correct
3 Correct 485 ms 12308 KB Output is correct
4 Correct 472 ms 12304 KB Output is correct
5 Correct 485 ms 12124 KB Output is correct
6 Correct 628 ms 12308 KB Output is correct
7 Correct 632 ms 12308 KB Output is correct
8 Correct 628 ms 12296 KB Output is correct
9 Correct 627 ms 12120 KB Output is correct
10 Correct 629 ms 12120 KB Output is correct
11 Correct 630 ms 12300 KB Output is correct
12 Correct 625 ms 12300 KB Output is correct
13 Correct 628 ms 12308 KB Output is correct
14 Correct 633 ms 12300 KB Output is correct
15 Correct 629 ms 12124 KB Output is correct
16 Correct 63 ms 2392 KB Output is correct
17 Correct 67 ms 2704 KB Output is correct
18 Correct 67 ms 2612 KB Output is correct
19 Correct 65 ms 2652 KB Output is correct
20 Correct 68 ms 2628 KB Output is correct
21 Execution timed out 2063 ms 15708 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12368 KB Output is correct
2 Correct 488 ms 12120 KB Output is correct
3 Correct 485 ms 12308 KB Output is correct
4 Correct 472 ms 12304 KB Output is correct
5 Correct 485 ms 12124 KB Output is correct
6 Correct 628 ms 12308 KB Output is correct
7 Correct 632 ms 12308 KB Output is correct
8 Correct 628 ms 12296 KB Output is correct
9 Correct 627 ms 12120 KB Output is correct
10 Correct 629 ms 12120 KB Output is correct
11 Correct 630 ms 12300 KB Output is correct
12 Correct 625 ms 12300 KB Output is correct
13 Correct 628 ms 12308 KB Output is correct
14 Correct 633 ms 12300 KB Output is correct
15 Correct 629 ms 12124 KB Output is correct
16 Correct 63 ms 2392 KB Output is correct
17 Correct 67 ms 2704 KB Output is correct
18 Correct 67 ms 2612 KB Output is correct
19 Correct 65 ms 2652 KB Output is correct
20 Correct 68 ms 2628 KB Output is correct
21 Execution timed out 2063 ms 15708 KB Time limit exceeded
22 Halted 0 ms 0 KB -