Submission #661139

#	Time	Username	Problem	Language	Result	Execution time	Memory
661139		activedeltorre	Boat (APIO16_boat)	C++14	31 / 100	565 ms	524288 KiB

boat

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
vector<int>norm;
map<int,int>mp;
pair<int,int>vec[505];
long long aib[1000005];
long long mod=1000000007;
int cnt=1;
void update(int poz,long val)
{
    while(poz<=cnt)
    {
        aib[poz]=(aib[poz]+val)%mod;
        poz=poz+(poz&(-poz));
    }
}
long long query(int poz)
{
    long long suma=0;
    while(poz>0)
    {
        suma=(suma+aib[poz])%mod;
        poz=poz-(poz&(-poz));
    }
    return suma;
}
int dp[10000005];
int main()
{
    long long val,n,i,j,k,x;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>vec[i].first;
        cin>>vec[i].second;
        for(j=vec[i].first;j<=vec[i].second;j++)
        {
            norm.push_back(j);
        }
    }
    norm.push_back(0);
    sort(norm.begin(),norm.end());
    for(i=0;i<norm.size();i++)
    {
        if(mp[norm[i]]==0)
        {
            mp[norm[i]]=cnt;
            cnt++;
        }
    }
    ///la poz 1 se alfa adaca nu tirmite barci
    update(1,1);
    for(i=1;i<n;i++)
    {
        for(j=vec[i].second;j>=vec[i].first;j--)
        {
            x=mp[j];
            val=query(x-1);
            update(x,val);
        }
    }
    long long suma=-1;
    for(j=vec[i].second;j>=vec[i].first;j--)
    {
        x=mp[j];
        suma=(suma+query(x-1))%mod;
    }
    suma=(suma+query(cnt))%mod;
    cout<<suma;
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(i=0;i<norm.size();i++)
      |             ~^~~~~~~~~~~~
boat.cpp:34:25: warning: unused variable 'k' [-Wunused-variable]
   34 |     long long val,n,i,j,k,x;
      |                         ^

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42