oj.uz

Submission #1092758

# Submission time Handle Problem Language Result Execution time Memory
1092758 2024-09-25T01:51:21 Z modwwe Escape Route 2 (JOI24_escape2) C++17
23 / 100
 303 ms 46420 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];
ib d[100001];
ib st[17][100001];
vector<int> vv;
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);
        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.back()+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<=n; 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;
        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;
            for(int j=0; j<17; j++)
                if(bit(s,j))
                    s4+=st[j][s3].b,s3=st[j][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
    }
}

Compilation message

Main.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 38 ms 8100 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 69 ms 9752 KB Output is correct
5 Correct 60 ms 8848 KB Output is correct
6 Correct 75 ms 9776 KB Output is correct
7 Correct 75 ms 9724 KB Output is correct
8 Correct 56 ms 8784 KB Output is correct
9 Correct 86 ms 9696 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 38 ms 8100 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 69 ms 9752 KB Output is correct
5 Correct 60 ms 8848 KB Output is correct
6 Correct 75 ms 9776 KB Output is correct
7 Correct 75 ms 9724 KB Output is correct
8 Correct 56 ms 8784 KB Output is correct
9 Correct 86 ms 9696 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Incorrect 67 ms 7684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 38 ms 8100 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 69 ms 9752 KB Output is correct
5 Correct 60 ms 8848 KB Output is correct
6 Correct 75 ms 9776 KB Output is correct
7 Correct 75 ms 9724 KB Output is correct
8 Correct 56 ms 8784 KB Output is correct
9 Correct 86 ms 9696 KB Output is correct
10 Correct 173 ms 37104 KB Output is correct
11 Correct 284 ms 46192 KB Output is correct
12 Correct 258 ms 46420 KB Output is correct
13 Correct 232 ms 45136 KB Output is correct
14 Correct 285 ms 46164 KB Output is correct
15 Correct 303 ms 46312 KB Output is correct
16 Correct 164 ms 37204 KB Output is correct
17 Correct 298 ms 46164 KB Output is correct
18 Correct 105 ms 39536 KB Output is correct
19 Correct 89 ms 39248 KB Output is correct
20 Correct 127 ms 39416 KB Output is correct
21 Correct 103 ms 39488 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 38 ms 8100 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 69 ms 9752 KB Output is correct
5 Correct 60 ms 8848 KB Output is correct
6 Correct 75 ms 9776 KB Output is correct
7 Correct 75 ms 9724 KB Output is correct
8 Correct 56 ms 8784 KB Output is correct
9 Correct 86 ms 9696 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Incorrect 67 ms 7684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5224 KB Output is correct
3 Incorrect 276 ms 10756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 38 ms 8100 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 69 ms 9752 KB Output is correct
5 Correct 60 ms 8848 KB Output is correct
6 Correct 75 ms 9776 KB Output is correct
7 Correct 75 ms 9724 KB Output is correct
8 Correct 56 ms 8784 KB Output is correct
9 Correct 86 ms 9696 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Incorrect 67 ms 7684 KB Output isn't correct
12 Halted 0 ms 0 KB -