Submission #480926

#	Time	Username	Problem	Language	Result	Execution time	Memory
480926		DJeniUp	Toll (BOI17_toll)	C++17	56 / 100	3079 ms	11132 KiB

toll

#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll k,n,m,o,res[10007],t[50007][7];

vector<pairll>v[50007];

struct D{
    ll l,r,q;
}d[10007];

bool mcp(D d1, D d2){
    if(d1.l/k==d2.l/k)return d1.r>d2.r;
    return d1.l<d2.l;
}

int main() {
    

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cin>>k>>n>>m>>o;
    scanf("%lld %lld %lld %lld", &k, &n, &m, &o);
    for(int i=1;i<=m;i++){
        ll l,r,c;
        //cin>>l>>r>>c;
        scanf("%lld %lld %lld", &l, &r, &c);
        v[r].pb({l,c});
    }
    for(int i=1;i<=o;i++){
        //cin>>d[i].l>>d[i].r;
        scanf("%lld %lld", &d[i].l, &d[i].r);
        d[i].q=i;
    }
    sort(d+1,d+1+o,mcp);
    ll x=0;
    for(int i=1;i<=o;i++){
        if(d[i].l/k!=d[i-1].l/k || i==1){
            x=d[i].l-d[i].l%k;
            for(int j=0;j<k;j++){
                t[x][j]=t[x+1][j]=t[x+2][j]=t[x+3][j]=t[x+4][j]=INF;
            }
            t[x][0]=t[x+1][1]=t[x+2][2]=t[x+3][3]=t[x+4][4]=0;
            for(int j=x+k;j<=d[i].r;j++){
                for(int y=0;y<k;y++){
                    t[j][y]=INF;
                    for(auto it: v[j]){
                        t[j][y]=min(t[j][y],t[it.fr][y]+it.sc);
                    }
                }
            }
        }
        if(d[i].l>d[i].r || t[d[i].r][d[i].l%k]==INF)res[d[i].q]=-1;
        else res[d[i].q]=t[d[i].r][d[i].l%k];
    }
    for(int i=1;i<=o;i++){
        //cout<<res[i]<<endl;
        printf("%lld\n", res[i]);
    }

}

Compilation message (stderr)

toll.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("O3")
      | 
toll.cpp: In function 'int main()':
toll.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%lld %lld %lld %lld", &k, &n, &m, &o);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld %lld %lld", &l, &r, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld %lld", &d[i].l, &d[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44