oj.uz

Submission #946360

# Submission time Handle Problem Language Result Execution time Memory
946360 2024-03-14T14:26:42 Z simona1230 Boat (APIO16_boat) C++17
9 / 100
 178 ms 8796 KB 
#include <bits/stdc++.h>

using namespace std;
long long n;
struct school
{
    int first,second,i;
    school(){}
    school(int _l,int _r,int _i)
    {
        first=_l;
        second=_r;
        i=_i;
    }
};
school p[200001];
school a[200001];
bool cmp(school s1,school s2)
{
    return s1.first<=s2.first;
}
bool cmp2(school s1,school s2)
{
    return s1.i<s2.i;
}
int lim;
void read()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        p[i]={x,y,i};
    }
    sort(p+1,p+n+1,cmp);

    long long last=0;
    for(long long i=1;i<=n;i++)
    {
        a[i].i=p[i].i;
        long long len=p[i].second-p[i].first;
        a[i].first=a[i-1].second+1;

        if(p[i-1].second>=p[i].first)
        {
            long long same=p[i-1].second-p[i].first;
            a[i].first=a[i-1].second-same;
        }

        a[i].second=a[i].first+len;
        //cout<<a[i].first<<" "<<a[i].second<<endl;
    }
    lim=a[n].second;
    sort(a+1,a+n+1,cmp2);
}

const long long mod=1e9+7;
long long t[4000001];

long long query(long long i,long long l,long long r,long long ql,long long qr)
{
    if(ql>qr)return 0;
    if(l>=ql&&r<=qr)
    {
        //cout<<i<<" "<<l<<" "<<r<<" "<<t[i]<<" query"<<endl;
        return t[i];
    }
    long long m=(l+r)/2;
    return (query(i*2,l,m,ql,min(qr,m))+query(i*2+1,m+1,r,max(ql,m+1),qr))%mod;
}

void update(long long i,long long l,long long r,long long idx,long long val)
{
    if(l==r)
    {
        t[i]+=val;
        t[i]%=mod;
        return;
    }
    long long m=(l+r)/2;
    if(m>=idx)update(i*2,l,m,idx,val);
    else update(i*2+1,m+1,r,idx,val);
    t[i]=t[i*2]+t[i*2+1];
    t[i]%=mod;
    //cout<<i<<" "<<l<<" "<<r<<" "<<t[i]<<endl;
}
void solve()
{
    update(1,0,lim,0,1);

    for(long long i=1;i<=n;i++)
    {
        //cout<<a[i].first<<" "<<a[i].second<<endl;
        for(long long j=a[i].second;j>=a[i].first;j--)
        {
            long long help=query(1,0,lim,0,j-1);
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            update(1,0,lim,j,help);
        }
    }
    int fin=query(1,0,lim,1,lim);
    cout<<fin<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}
/*
3
4 10
7 15
1 4
*/

Compilation message

boat.cpp: In function 'void read()':
boat.cpp:34:19: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   34 |         p[i]={x,y,i};
      |                   ^
boat.cpp:38:15: warning: unused variable 'last' [-Wunused-variable]
   38 |     long long last=0;
      |               ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4600 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4568 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4576 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4600 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4568 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4576 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 178 ms 4700 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8796 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 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4600 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4568 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4576 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Incorrect 178 ms 4700 KB Output isn't correct
22 Halted 0 ms 0 KB -