| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 500846 | 2022-01-01T12:19:42 Z | mars4 | Toll (BOI17_toll) | C++17 | 311 ms | 169924 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define ll int64_t
#define ld long double
#define nl cout<<"\n"
#define all(v) v.begin(),v.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define forn(i,a,b) for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b) for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1'000'000'007
#define mod2 998'244'353
#define inf 1'000'000'000'000'007
#define pi 3.14159265358979323846
template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;
template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p) {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s) {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m) {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}
void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail>
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
//---------------------------------mars4---------------------------------
ll dp[50000][17][5][5];
void combine(ll a[5][5],ll b[5][5],ll c[5][5])
{
forn(i,0,5)
{
forn(j,0,5)
{
forn(k,0,5)
{
a[i][k]=min(a[i][k],b[i][j]+c[j][k]);
}
}
}
}
int main()
{
fastio();
ll z,n,m,t,k,i,j,l,d,h,r;
mset(dp,0x3f);
ll q;
cin>>k>>n>>m>>q;
forn(i,0,m)
{
cin>>l>>r>>d;
dp[l/k][0][l%k][r%k]=d;
}
for(int j=1;j<17;j++)
{
for(int i=0;i+(1ll<<j)<(n+k-1)/k;i++)
{
combine(dp[i][j],dp[i][j-1],dp[i+(1ll<<(j-1))][j-1]);
}
}
forn(i,0,q)
{
cin>>l>>r;
ll cl=l,cr=r;
l/=k;
r/=k;
ll res[5][5];
mset(res,0x0f);
forn(j,0,5)
{
res[j][j]=0;
}
for(ll j=16;j>=0;j--)
{
if(l+(1ll<<j)<=r)
{
ll nres[5][5];
mset(nres,0x3f);
combine(nres,res,dp[l][j]);
forn(i1,0,5)
{
forn(j1,0,5)
{
res[i1][j1]=nres[i1][j1];
}
}
l+=(1ll<<j);
}
}
if(res[cl%k][cr%k]>=inf)
{
cout<<"-1\n";
}
else
{
cout<<res[cl%k][cr%k]<<"\n";
}
}
cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 299 ms | 167668 KB | Output is correct |
| 2 | Correct | 68 ms | 166616 KB | Output is correct |
| 3 | Correct | 63 ms | 166596 KB | Output is correct |
| 4 | Correct | 64 ms | 166624 KB | Output is correct |
| 5 | Correct | 85 ms | 166536 KB | Output is correct |
| 6 | Correct | 75 ms | 166632 KB | Output is correct |
| 7 | Correct | 68 ms | 166596 KB | Output is correct |
| 8 | Correct | 279 ms | 167568 KB | Output is correct |
| 9 | Correct | 291 ms | 167544 KB | Output is correct |
| 10 | Correct | 271 ms | 166800 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 201 ms | 168256 KB | Output is correct |
| 2 | Correct | 67 ms | 166568 KB | Output is correct |
| 3 | Correct | 63 ms | 166600 KB | Output is correct |
| 4 | Correct | 64 ms | 166540 KB | Output is correct |
| 5 | Correct | 64 ms | 166580 KB | Output is correct |
| 6 | Correct | 64 ms | 166552 KB | Output is correct |
| 7 | Correct | 83 ms | 166664 KB | Output is correct |
| 8 | Correct | 93 ms | 166724 KB | Output is correct |
| 9 | Correct | 271 ms | 167620 KB | Output is correct |
| 10 | Correct | 176 ms | 168900 KB | Output is correct |
| 11 | Correct | 219 ms | 168320 KB | Output is correct |
| 12 | Correct | 155 ms | 168008 KB | Output is correct |
| 13 | Correct | 120 ms | 169044 KB | Output is correct |
| 14 | Correct | 136 ms | 168076 KB | Output is correct |
| 15 | Correct | 98 ms | 167744 KB | Output is correct |
| 16 | Correct | 100 ms | 167824 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 70 ms | 166568 KB | Output is correct |
| 2 | Correct | 69 ms | 166596 KB | Output is correct |
| 3 | Correct | 66 ms | 166680 KB | Output is correct |
| 4 | Correct | 64 ms | 166532 KB | Output is correct |
| 5 | Correct | 65 ms | 166512 KB | Output is correct |
| 6 | Correct | 77 ms | 166596 KB | Output is correct |
| 7 | Correct | 84 ms | 166628 KB | Output is correct |
| 8 | Correct | 68 ms | 166600 KB | Output is correct |
| 9 | Correct | 65 ms | 166660 KB | Output is correct |
| 10 | Correct | 311 ms | 167364 KB | Output is correct |
| 11 | Correct | 186 ms | 168156 KB | Output is correct |
| 12 | Correct | 162 ms | 168808 KB | Output is correct |
| 13 | Correct | 159 ms | 168948 KB | Output is correct |
| 14 | Correct | 150 ms | 168484 KB | Output is correct |
| 15 | Correct | 98 ms | 167748 KB | Output is correct |
| 16 | Correct | 125 ms | 167784 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 70 ms | 166568 KB | Output is correct |
| 2 | Correct | 69 ms | 166596 KB | Output is correct |
| 3 | Correct | 66 ms | 166680 KB | Output is correct |
| 4 | Correct | 64 ms | 166532 KB | Output is correct |
| 5 | Correct | 65 ms | 166512 KB | Output is correct |
| 6 | Correct | 77 ms | 166596 KB | Output is correct |
| 7 | Correct | 84 ms | 166628 KB | Output is correct |
| 8 | Correct | 68 ms | 166600 KB | Output is correct |
| 9 | Correct | 65 ms | 166660 KB | Output is correct |
| 10 | Correct | 311 ms | 167364 KB | Output is correct |
| 11 | Correct | 186 ms | 168156 KB | Output is correct |
| 12 | Correct | 162 ms | 168808 KB | Output is correct |
| 13 | Correct | 159 ms | 168948 KB | Output is correct |
| 14 | Correct | 150 ms | 168484 KB | Output is correct |
| 15 | Correct | 98 ms | 167748 KB | Output is correct |
| 16 | Correct | 125 ms | 167784 KB | Output is correct |
| 17 | Correct | 182 ms | 168260 KB | Output is correct |
| 18 | Correct | 67 ms | 166616 KB | Output is correct |
| 19 | Correct | 70 ms | 166520 KB | Output is correct |
| 20 | Correct | 63 ms | 166580 KB | Output is correct |
| 21 | Correct | 65 ms | 166548 KB | Output is correct |
| 22 | Correct | 65 ms | 166556 KB | Output is correct |
| 23 | Correct | 69 ms | 166684 KB | Output is correct |
| 24 | Correct | 85 ms | 166700 KB | Output is correct |
| 25 | Correct | 82 ms | 166708 KB | Output is correct |
| 26 | Correct | 71 ms | 166604 KB | Output is correct |
| 27 | Correct | 272 ms | 167476 KB | Output is correct |
| 28 | Correct | 162 ms | 168860 KB | Output is correct |
| 29 | Correct | 182 ms | 169096 KB | Output is correct |
| 30 | Correct | 159 ms | 168460 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 299 ms | 167668 KB | Output is correct |
| 2 | Correct | 68 ms | 166616 KB | Output is correct |
| 3 | Correct | 63 ms | 166596 KB | Output is correct |
| 4 | Correct | 64 ms | 166624 KB | Output is correct |
| 5 | Correct | 85 ms | 166536 KB | Output is correct |
| 6 | Correct | 75 ms | 166632 KB | Output is correct |
| 7 | Correct | 68 ms | 166596 KB | Output is correct |
| 8 | Correct | 279 ms | 167568 KB | Output is correct |
| 9 | Correct | 291 ms | 167544 KB | Output is correct |
| 10 | Correct | 271 ms | 166800 KB | Output is correct |
| 11 | Correct | 201 ms | 168256 KB | Output is correct |
| 12 | Correct | 67 ms | 166568 KB | Output is correct |
| 13 | Correct | 63 ms | 166600 KB | Output is correct |
| 14 | Correct | 64 ms | 166540 KB | Output is correct |
| 15 | Correct | 64 ms | 166580 KB | Output is correct |
| 16 | Correct | 64 ms | 166552 KB | Output is correct |
| 17 | Correct | 83 ms | 166664 KB | Output is correct |
| 18 | Correct | 93 ms | 166724 KB | Output is correct |
| 19 | Correct | 271 ms | 167620 KB | Output is correct |
| 20 | Correct | 176 ms | 168900 KB | Output is correct |
| 21 | Correct | 219 ms | 168320 KB | Output is correct |
| 22 | Correct | 155 ms | 168008 KB | Output is correct |
| 23 | Correct | 120 ms | 169044 KB | Output is correct |
| 24 | Correct | 136 ms | 168076 KB | Output is correct |
| 25 | Correct | 98 ms | 167744 KB | Output is correct |
| 26 | Correct | 100 ms | 167824 KB | Output is correct |
| 27 | Correct | 70 ms | 166568 KB | Output is correct |
| 28 | Correct | 69 ms | 166596 KB | Output is correct |
| 29 | Correct | 66 ms | 166680 KB | Output is correct |
| 30 | Correct | 64 ms | 166532 KB | Output is correct |
| 31 | Correct | 65 ms | 166512 KB | Output is correct |
| 32 | Correct | 77 ms | 166596 KB | Output is correct |
| 33 | Correct | 84 ms | 166628 KB | Output is correct |
| 34 | Correct | 68 ms | 166600 KB | Output is correct |
| 35 | Correct | 65 ms | 166660 KB | Output is correct |
| 36 | Correct | 311 ms | 167364 KB | Output is correct |
| 37 | Correct | 186 ms | 168156 KB | Output is correct |
| 38 | Correct | 162 ms | 168808 KB | Output is correct |
| 39 | Correct | 159 ms | 168948 KB | Output is correct |
| 40 | Correct | 150 ms | 168484 KB | Output is correct |
| 41 | Correct | 98 ms | 167748 KB | Output is correct |
| 42 | Correct | 125 ms | 167784 KB | Output is correct |
| 43 | Correct | 182 ms | 168260 KB | Output is correct |
| 44 | Correct | 67 ms | 166616 KB | Output is correct |
| 45 | Correct | 70 ms | 166520 KB | Output is correct |
| 46 | Correct | 63 ms | 166580 KB | Output is correct |
| 47 | Correct | 65 ms | 166548 KB | Output is correct |
| 48 | Correct | 65 ms | 166556 KB | Output is correct |
| 49 | Correct | 69 ms | 166684 KB | Output is correct |
| 50 | Correct | 85 ms | 166700 KB | Output is correct |
| 51 | Correct | 82 ms | 166708 KB | Output is correct |
| 52 | Correct | 71 ms | 166604 KB | Output is correct |
| 53 | Correct | 272 ms | 167476 KB | Output is correct |
| 54 | Correct | 162 ms | 168860 KB | Output is correct |
| 55 | Correct | 182 ms | 169096 KB | Output is correct |
| 56 | Correct | 159 ms | 168460 KB | Output is correct |
| 57 | Correct | 173 ms | 169924 KB | Output is correct |
| 58 | Correct | 291 ms | 167488 KB | Output is correct |
| 59 | Correct | 204 ms | 168428 KB | Output is correct |