oj.uz

Submission #1094268

# Submission time Handle Problem Language Result Execution time Memory
1094268 2024-09-29T08:52:52 Z modwwe Escape Route 2 (JOI24_escape2) C++17
54 / 100
 318 ms 54868 KB 
#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=30;
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+1;
    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++)
    {

        if(v[i].size()!=0)
        {
                    for(int j=1; j<=b[i];j++)
            dp[j]= {c[i][j],0};
            sort(v[i].begin(),v[i].end(),cmp);
            bool de=0;
            s4=i;
            for(auto x:v[i])
            {
                if(x.a==s9){ans[x.b]=s6; continue;}
                s6=inf;
                if(x.a<=f[i])
                {
                    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&-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&-s);
                                s5+=st[s7][s3].b;
                                s3=st[s7][s3].a;
                            }
                            //dp[j]= {s3,s5};
                            cd[s3]=min(cd[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&-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);
                    }
                }
                s9=x.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:192:29: warning: statement has no effect [-Wunused-value]
  192 |                         for(s; s; s-=s&-s)
      |                             ^
Main.cpp:214:33: warning: statement has no effect [-Wunused-value]
  214 |                             for(s; s; s-=s&-s)
      |                                 ^
Main.cpp:231:29: warning: statement has no effect [-Wunused-value]
  231 |                         for(s; s; s-=s&-s)
      |                             ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 40 ms 13596 KB Output is correct
3 Correct 58 ms 14288 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 64 ms 14528 KB Output is correct
6 Correct 76 ms 15956 KB Output is correct
7 Correct 82 ms 16052 KB Output is correct
8 Correct 56 ms 14052 KB Output is correct
9 Correct 83 ms 15956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 40 ms 13596 KB Output is correct
3 Correct 58 ms 14288 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 64 ms 14528 KB Output is correct
6 Correct 76 ms 15956 KB Output is correct
7 Correct 82 ms 16052 KB Output is correct
8 Correct 56 ms 14052 KB Output is correct
9 Correct 83 ms 15956 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 72 ms 15220 KB Output is correct
12 Correct 72 ms 15184 KB Output is correct
13 Correct 71 ms 15252 KB Output is correct
14 Correct 72 ms 15200 KB Output is correct
15 Correct 75 ms 15444 KB Output is correct
16 Correct 43 ms 13760 KB Output is correct
17 Correct 69 ms 15840 KB Output is correct
18 Correct 86 ms 15480 KB Output is correct
19 Correct 79 ms 15952 KB Output is correct
20 Correct 70 ms 15592 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 40 ms 13596 KB Output is correct
3 Correct 58 ms 14288 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 64 ms 14528 KB Output is correct
6 Correct 76 ms 15956 KB Output is correct
7 Correct 82 ms 16052 KB Output is correct
8 Correct 56 ms 14052 KB Output is correct
9 Correct 83 ms 15956 KB Output is correct
10 Correct 183 ms 44208 KB Output is correct
11 Correct 279 ms 54868 KB Output is correct
12 Correct 286 ms 54868 KB Output is correct
13 Correct 247 ms 52916 KB Output is correct
14 Correct 290 ms 54864 KB Output is correct
15 Correct 318 ms 54868 KB Output is correct
16 Correct 205 ms 44012 KB Output is correct
17 Correct 289 ms 54788 KB Output is correct
18 Correct 114 ms 45092 KB Output is correct
19 Correct 105 ms 44628 KB Output is correct
20 Correct 111 ms 45044 KB Output is correct
21 Correct 109 ms 45136 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 40 ms 13596 KB Output is correct
3 Correct 58 ms 14288 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 64 ms 14528 KB Output is correct
6 Correct 76 ms 15956 KB Output is correct
7 Correct 82 ms 16052 KB Output is correct
8 Correct 56 ms 14052 KB Output is correct
9 Correct 83 ms 15956 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 72 ms 15220 KB Output is correct
12 Correct 72 ms 15184 KB Output is correct
13 Correct 71 ms 15252 KB Output is correct
14 Correct 72 ms 15200 KB Output is correct
15 Correct 75 ms 15444 KB Output is correct
16 Correct 43 ms 13760 KB Output is correct
17 Correct 69 ms 15840 KB Output is correct
18 Correct 86 ms 15480 KB Output is correct
19 Correct 79 ms 15952 KB Output is correct
20 Correct 70 ms 15592 KB Output is correct
21 Correct 183 ms 44208 KB Output is correct
22 Correct 279 ms 54868 KB Output is correct
23 Correct 286 ms 54868 KB Output is correct
24 Correct 247 ms 52916 KB Output is correct
25 Correct 290 ms 54864 KB Output is correct
26 Correct 318 ms 54868 KB Output is correct
27 Correct 205 ms 44012 KB Output is correct
28 Correct 289 ms 54788 KB Output is correct
29 Correct 114 ms 45092 KB Output is correct
30 Correct 105 ms 44628 KB Output is correct
31 Correct 111 ms 45044 KB Output is correct
32 Correct 109 ms 45136 KB Output is correct
33 Correct 271 ms 48540 KB Output is correct
34 Correct 242 ms 48464 KB Output is correct
35 Correct 241 ms 45648 KB Output is correct
36 Correct 215 ms 45392 KB Output is correct
37 Correct 225 ms 46488 KB Output is correct
38 Correct 200 ms 42464 KB Output is correct
39 Correct 263 ms 52048 KB Output is correct
40 Correct 193 ms 39760 KB Output is correct
41 Correct 177 ms 42840 KB Output is correct
42 Correct 260 ms 53588 KB Output is correct
43 Correct 195 ms 48976 KB Output is correct
44 Correct 249 ms 51028 KB Output is correct
45 Correct 124 ms 43604 KB Output is correct
46 Correct 100 ms 41168 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7660 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Incorrect 102 ms 41088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 40 ms 13596 KB Output is correct
3 Correct 58 ms 14288 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 64 ms 14528 KB Output is correct
6 Correct 76 ms 15956 KB Output is correct
7 Correct 82 ms 16052 KB Output is correct
8 Correct 56 ms 14052 KB Output is correct
9 Correct 83 ms 15956 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 72 ms 15220 KB Output is correct
12 Correct 72 ms 15184 KB Output is correct
13 Correct 71 ms 15252 KB Output is correct
14 Correct 72 ms 15200 KB Output is correct
15 Correct 75 ms 15444 KB Output is correct
16 Correct 43 ms 13760 KB Output is correct
17 Correct 69 ms 15840 KB Output is correct
18 Correct 86 ms 15480 KB Output is correct
19 Correct 79 ms 15952 KB Output is correct
20 Correct 70 ms 15592 KB Output is correct
21 Correct 183 ms 44208 KB Output is correct
22 Correct 279 ms 54868 KB Output is correct
23 Correct 286 ms 54868 KB Output is correct
24 Correct 247 ms 52916 KB Output is correct
25 Correct 290 ms 54864 KB Output is correct
26 Correct 318 ms 54868 KB Output is correct
27 Correct 205 ms 44012 KB Output is correct
28 Correct 289 ms 54788 KB Output is correct
29 Correct 114 ms 45092 KB Output is correct
30 Correct 105 ms 44628 KB Output is correct
31 Correct 111 ms 45044 KB Output is correct
32 Correct 109 ms 45136 KB Output is correct
33 Correct 271 ms 48540 KB Output is correct
34 Correct 242 ms 48464 KB Output is correct
35 Correct 241 ms 45648 KB Output is correct
36 Correct 215 ms 45392 KB Output is correct
37 Correct 225 ms 46488 KB Output is correct
38 Correct 200 ms 42464 KB Output is correct
39 Correct 263 ms 52048 KB Output is correct
40 Correct 193 ms 39760 KB Output is correct
41 Correct 177 ms 42840 KB Output is correct
42 Correct 260 ms 53588 KB Output is correct
43 Correct 195 ms 48976 KB Output is correct
44 Correct 249 ms 51028 KB Output is correct
45 Correct 124 ms 43604 KB Output is correct
46 Correct 100 ms 41168 KB Output is correct
47 Correct 4 ms 7660 KB Output is correct
48 Correct 4 ms 7516 KB Output is correct
49 Incorrect 102 ms 41088 KB Output isn't correct
50 Halted 0 ms 0 KB -