#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e17;
const int mod2 = 1e9 + 9;
const int mod1 = 998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, l, r, mid, l2, r2, center;
int i, s10, s12,k1,k2,s11;
int kk;
int el = 19;
main()
{
//fin(task);
//fou(task);
NHP
/// cin>>s1;
///modwwe
phongbeo();
// checktime
}
int S=50;
int s,t;
vector<ib> a[100001];
int b[100001];
vector<int> c[100001];
ib d[100001];
ib st[17][100001];
vector<int> vv;
vector<ib> v[100001];
vector<int> dp[318];
int ans[100001];
bool f[100001];
int pos[100001];
int prefix_b[100001];
int rig[100001];
bool cmp(ib a,ib b)
{
return a.a<b.a;
}
int get(int l,int j,int r)
{
s=r-l-1;
s3=c[l][j];
s4=0;/// 3->4->0
for(int f=0; f<17; f++)
if(bit(s,f))
s4+=st[f][s3].b,s3=st[f][s3].a;
return s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a;
}
void setup()
{
s2=n+1;
dem=0;
for(int i=n-1; i>=1; --i)
{
if(b[i]<=S)
s2=i;
if(s2!=i&&f[i]&&s2!=n+1)
{
s3=s2-i;
pos[i]=dem++;
dp[dem].resize(330);
rig[i]=s2;
for(int j=1; j<=319; j++)
dp[dem][j]=inf;
for(int j=1; j<=b[i]; j++)
{
s4=c[i][j];
s=0;
for(int j=17; j>=0; --j)
if(bit(s3,j))
s+=st[j][s4].b,s4=st[j][s4].a;
dp[dem][s4-prefix_b[s2-1]]=min(s,dp[dem][s4-prefix_b[s2-1]]);
}
}
}
}
void phongbeo()
{
cin>>n>>t;
for(int i=1; i<n; i++)
{
cin>>k;
b[i]=k;
a[i].resize(k+1);
c[i].resize(k+1);
prefix_b[i]=b[i]+prefix_b[i-1];
s9+=k;
for(int j=1; j<=k; j++)
cin>>a[i][j].a>>a[i][j].b,c[i][j]=++dem,d[dem]= {i,j};
sort(a[i].begin()+1,a[i].end(),cmp);
for(int j=k-1; j>=1; --j)
a[i][j].b=min(a[i][j].b,a[i][j+1].b);
}
for(int i=1; i<n-1; i++)
{
vv.clear();
for(int j=1; j<=b[i+1]; j++)
vv.pb(a[i+1][j].a);
for(int j=1; j<=b[i]; j++)
{
if(a[i][j].b>vv.back())
{
s3=vv[0]+t-a[i][j].a;
st[0][c[i][j]]= {c[i+1][1],s3};
}
else
{
s2=lower_bound(vv.begin(),vv.end(),a[i][j].b)-vv.begin()+1;
s3=a[i+1][s2].a-a[i][j].a;
st[0][c[i][j]]= {c[i+1][s2],s3};
}
}
}
for(int i=1; i<17; i++)
for(int j=1; j<=s9; j++)
st[i][j].a=st[i-1][st[i-1][j].a].a,
st[i][j].b=st[i-1][j].b+st[i-1][st[i-1][j].a].b;
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>l>>r;
v[l].pb({r,i});
f[l]=1;
/* if(l==r)
{
cout<<0,down continue;
}
for(int j=1; j<=b[l]; j++)
{
s=r-l-1;
s3=c[l][j];
s4=0;/// 3->4->0
for(int f=0; f<17; f++)
if(bit(s,f))
s4+=st[f][s3].b,s3=st[f][s3].a;
if(j==1)s5=s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a;
else s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a,s5);
}
cout<<s5,down*/
}
setup();
for(int i=1; i<=n; i++)
{
for(auto x:v[i])
{
s5=inf;
if(b[i]<=S||x.a<=rig[i])
{
for(int j=1; j<=b[i]; j++)
{
r=x.a;
l=i;
s=r-l-1;
s3=c[l][j];
s4=0;/// 3->4->0
for(int f=0; f<17; f++)
if(bit(s,f))
s4+=st[f][s3].b,s3=st[f][s3].a;
s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a,s5);
}
}
else
{
l=rig[i];
for(int j=1; j<=b[l]; j++)
{
if(dp[pos[i]][c[l][j]-prefix_b[l-1]]==inf) continue;
r=x.a;
s=r-l-1;
s3=c[l][j];
s4=0;/// 3->4->0
for(int f=0; f<17; f++)
if(bit(s,f))
s4+=st[f][s3].b,s3=st[f][s3].a;
s5=min(s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a+dp[pos[i]][c[l][j]-prefix_b[l-1]],s5);
}
}
ans[x.b]=s5;
}
s2=1;
}
for(int i=1; i<=m; i++)
cout<<ans[i],down
}
Compilation message
Main.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
67 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
30704 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
30704 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
30704 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
30704 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7516 KB |
Output is correct |
| 3 |
Incorrect |
50 ms |
42120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
30704 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
