oj.uz

Submission #946405

# Submission time Handle Problem Language Result Execution time Memory
946405 2024-03-14T15:59:05 Z simona1230 Boat (APIO16_boat) C++17
31 / 100
 358 ms 18976 KB 
#include <bits/stdc++.h>

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

    long long last=0,oglast=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=lim+1;

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

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

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

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<<" "<<help<<endl;
            update(1,0,lim,j,help);
        }
    }
    long long 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

4
10 15
12 20
12 17
30 40

3
10 20
50 60
5 25

3038 8036
9906 17068
1718 10410

500 600
800 900
100 850
*/

Compilation message

boat.cpp: In function 'void read()':
boat.cpp:38:15: warning: unused variable 'last' [-Wunused-variable]
   38 |     long long last=0,oglast=0;
      |               ^~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2548 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 177 ms 2636 KB Output is correct
22 Correct 177 ms 2628 KB Output is correct
23 Correct 165 ms 2624 KB Output is correct
24 Correct 194 ms 2396 KB Output is correct
25 Correct 188 ms 2628 KB Output is correct
26 Correct 188 ms 2396 KB Output is correct
27 Correct 190 ms 2396 KB Output is correct
28 Correct 190 ms 2564 KB Output is correct
29 Correct 194 ms 2572 KB Output is correct
30 Correct 322 ms 18728 KB Output is correct
31 Correct 320 ms 18756 KB Output is correct
32 Correct 358 ms 18976 KB Output is correct
33 Correct 350 ms 18672 KB Output is correct
34 Correct 316 ms 18780 KB Output is correct
35 Correct 301 ms 18832 KB Output is correct
36 Correct 308 ms 18848 KB Output is correct
37 Correct 321 ms 18768 KB Output is correct
38 Correct 305 ms 18772 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4696 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2516 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2548 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 177 ms 2636 KB Output is correct
22 Correct 177 ms 2628 KB Output is correct
23 Correct 165 ms 2624 KB Output is correct
24 Correct 194 ms 2396 KB Output is correct
25 Correct 188 ms 2628 KB Output is correct
26 Correct 188 ms 2396 KB Output is correct
27 Correct 190 ms 2396 KB Output is correct
28 Correct 190 ms 2564 KB Output is correct
29 Correct 194 ms 2572 KB Output is correct
30 Correct 322 ms 18728 KB Output is correct
31 Correct 320 ms 18756 KB Output is correct
32 Correct 358 ms 18976 KB Output is correct
33 Correct 350 ms 18672 KB Output is correct
34 Correct 316 ms 18780 KB Output is correct
35 Correct 301 ms 18832 KB Output is correct
36 Correct 308 ms 18848 KB Output is correct
37 Correct 321 ms 18768 KB Output is correct
38 Correct 305 ms 18772 KB Output is correct
39 Runtime error 3 ms 4696 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -