oj.uz

Submission #984135

# Submission time Handle Problem Language Result Execution time Memory
984135 2024-05-16T10:31:44 Z Aiperiii Boat (APIO16_boat) C++14
9 / 100
 2000 ms 15960 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[505];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    f[1]=1;
    for(int i=2;i<=500;i++){
        f[i]=f[i-1]*i;
        f[i]%=mod;
    }
    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:45: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]
   45 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:56: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]
   56 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:75: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]
   75 |         for(int j=0;j<r.size();j++){
      |                     ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12304 KB Output is correct
2 Correct 485 ms 12308 KB Output is correct
3 Correct 479 ms 12308 KB Output is correct
4 Correct 472 ms 12124 KB Output is correct
5 Correct 481 ms 12308 KB Output is correct
6 Correct 629 ms 12300 KB Output is correct
7 Correct 632 ms 12372 KB Output is correct
8 Correct 628 ms 12312 KB Output is correct
9 Correct 628 ms 12316 KB Output is correct
10 Correct 628 ms 12320 KB Output is correct
11 Correct 626 ms 12308 KB Output is correct
12 Correct 623 ms 12124 KB Output is correct
13 Correct 628 ms 12304 KB Output is correct
14 Correct 629 ms 12124 KB Output is correct
15 Correct 627 ms 12368 KB Output is correct
16 Correct 63 ms 2396 KB Output is correct
17 Correct 67 ms 2648 KB Output is correct
18 Correct 66 ms 2612 KB Output is correct
19 Correct 64 ms 2704 KB Output is correct
20 Correct 68 ms 2648 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12304 KB Output is correct
2 Correct 485 ms 12308 KB Output is correct
3 Correct 479 ms 12308 KB Output is correct
4 Correct 472 ms 12124 KB Output is correct
5 Correct 481 ms 12308 KB Output is correct
6 Correct 629 ms 12300 KB Output is correct
7 Correct 632 ms 12372 KB Output is correct
8 Correct 628 ms 12312 KB Output is correct
9 Correct 628 ms 12316 KB Output is correct
10 Correct 628 ms 12320 KB Output is correct
11 Correct 626 ms 12308 KB Output is correct
12 Correct 623 ms 12124 KB Output is correct
13 Correct 628 ms 12304 KB Output is correct
14 Correct 629 ms 12124 KB Output is correct
15 Correct 627 ms 12368 KB Output is correct
16 Correct 63 ms 2396 KB Output is correct
17 Correct 67 ms 2648 KB Output is correct
18 Correct 66 ms 2612 KB Output is correct
19 Correct 64 ms 2704 KB Output is correct
20 Correct 68 ms 2648 KB Output is correct
21 Execution timed out 2066 ms 15960 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 12304 KB Output is correct
2 Correct 485 ms 12308 KB Output is correct
3 Correct 479 ms 12308 KB Output is correct
4 Correct 472 ms 12124 KB Output is correct
5 Correct 481 ms 12308 KB Output is correct
6 Correct 629 ms 12300 KB Output is correct
7 Correct 632 ms 12372 KB Output is correct
8 Correct 628 ms 12312 KB Output is correct
9 Correct 628 ms 12316 KB Output is correct
10 Correct 628 ms 12320 KB Output is correct
11 Correct 626 ms 12308 KB Output is correct
12 Correct 623 ms 12124 KB Output is correct
13 Correct 628 ms 12304 KB Output is correct
14 Correct 629 ms 12124 KB Output is correct
15 Correct 627 ms 12368 KB Output is correct
16 Correct 63 ms 2396 KB Output is correct
17 Correct 67 ms 2648 KB Output is correct
18 Correct 66 ms 2612 KB Output is correct
19 Correct 64 ms 2704 KB Output is correct
20 Correct 68 ms 2648 KB Output is correct
21 Execution timed out 2066 ms 15960 KB Time limit exceeded
22 Halted 0 ms 0 KB -