#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,t;
vector<ib> a[100001];
int b[100001];
vector<int> c[100001];
int ans[300001];
ib d[100001];
ib st[17][100001];
int f[100001];
int cd[100001];
ib dp[100001];
vector<int> vv;
vector<ib> v[100001];
int S=0;
bool cmp(ib a,ib b)
{
return a.a<b.a;
}
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);
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;
s5=n;
for(int i=n-1; i>=1; --i)
{
if(b[i]<=S)s5=i;
f[i]=s5;
}
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>l>>r;
if(l==r)
{
ans[i]=0;
continue;
}
if(b[l]>S)
v[l].pb({r,i});
else
{
for(int j=1; j<=b[l]; j++)
{
s=r-l-1;
s3=c[l][j];
s4=0;
for(s; s; s-=s&-s)
{
int g=31-__builtin_clz(s&-s);
s4+=st[g][s3].b;
s3=st[g][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);
}
ans[i]=s5;
}
}
for(int i=1; i<n; i++)
{
for(int j=1; j<=b[i];j++)
dp[j]= {c[i][j],0};
if(v[i].size()!=0)
{
sort(v[i].begin(),v[i].end(),cmp);
bool de=0;
s4=i;
for(auto x:v[i])
{
s6=inf;
if(x.a<=n)
{
for(int j=1; j<=b[i]; j++)
{
s3=dp[j].a;
s5=dp[j].b;
s=x.a-s4-1;
for(s; s; s-=s&-s)
{
s7=31-__builtin_clz(s);
s5+=st[s7][s3].b;
s3=st[s7][s3].a;
}
s6=min(s6,s5+a[x.a-1][d[s3].b].b-a[x.a-1][d[s3].b].a);
dp[j]= {s3,s5};
}
s4=x.a-1;
}
else
{
if(!de)
{
for(int j=1; j<=b[f[i]]; j++)
cd[c[f[i]][j]]=inf;
for(int j=1; j<=b[i]; j++)
{
s3=dp[j].a;
s5=dp[j].b;
s=f[i]-s4;
for(s; s; s-=s&-s)
{
s7=31-__builtin_clz(s);
s5+=st[s7][s3].b;
s3=st[s7][s3].a;
}
s6=min(s6,s5+a[x.a-1][d[s3].b].b-a[x.a-1][d[s3].b].a);
//dp[j]= {s3,s5};
cd[s3]=min(f[s3],s5);
}
}
de=1;
for(int j=1; j<=b[f[i]]; j++)
{
s=x.a-f[i]-1;
s3=c[f[i]][j];
s5=cd[s3];
for(s; s; s-=s&-s)
{
s7=31-__builtin_clz(s);
s5+=st[s7][s3].b;
s3=st[s7][s3].a;
}
s6=min(s6,s5+a[x.a-1][d[s3].b].b-a[x.a-1][d[s3].b].a);
}
}
ans[x.b]=s6;
}
}
}
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()
| ^~~~
Main.cpp: In function 'void phongbeo()':
Main.cpp:158:21: warning: statement has no effect [-Wunused-value]
158 | for(s; s; s-=s&-s)
| ^
Main.cpp:190:29: warning: statement has no effect [-Wunused-value]
190 | for(s; s; s-=s&-s)
| ^
Main.cpp:212:33: warning: statement has no effect [-Wunused-value]
212 | for(s; s; s-=s&-s)
| ^
Main.cpp:229:29: warning: statement has no effect [-Wunused-value]
229 | for(s; s; s-=s&-s)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
49 ms |
17808 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
18772 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 |
Correct |
49 ms |
17808 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
18772 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 |
Correct |
49 ms |
17808 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
18772 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 |
Correct |
49 ms |
17808 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
18772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7640 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 3 |
Correct |
133 ms |
38780 KB |
Output is correct |
| 4 |
Correct |
130 ms |
41088 KB |
Output is correct |
| 5 |
Correct |
120 ms |
41296 KB |
Output is correct |
| 6 |
Correct |
116 ms |
41056 KB |
Output is correct |
| 7 |
Correct |
113 ms |
41288 KB |
Output is correct |
| 8 |
Correct |
122 ms |
41296 KB |
Output is correct |
| 9 |
Correct |
121 ms |
41368 KB |
Output is correct |
| 10 |
Execution timed out |
3039 ms |
38856 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
49 ms |
17808 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
18772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
