oj.uz

Submission #1092756

# Submission time Handle Problem Language Result Execution time Memory
1092756 2024-09-25T01:49:49 Z modwwe Escape Route 2 (JOI24_escape2) C++17
23 / 100
 324 ms 51920 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;
        }
        s=r-l-1;
        s3=c[l][1];
        s4=0;
        for(int j=0; j<17; j++)
            if(bit(s,j))
                s4+=st[j][s3].b,s3=st[j][s3].a;
        cout<<s4+a[r-1][d[s3].b].b-a[r-1][d[s3].b].a,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 3 ms 5212 KB Output is correct
2 Correct 38 ms 9376 KB Output is correct
3 Correct 55 ms 10580 KB Output is correct
4 Correct 73 ms 12372 KB Output is correct
5 Correct 61 ms 10900 KB Output is correct
6 Correct 85 ms 12384 KB Output is correct
7 Correct 79 ms 12504 KB Output is correct
8 Correct 59 ms 10592 KB Output is correct
9 Correct 82 ms 12384 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 38 ms 9376 KB Output is correct
3 Correct 55 ms 10580 KB Output is correct
4 Correct 73 ms 12372 KB Output is correct
5 Correct 61 ms 10900 KB Output is correct
6 Correct 85 ms 12384 KB Output is correct
7 Correct 79 ms 12504 KB Output is correct
8 Correct 59 ms 10592 KB Output is correct
9 Correct 82 ms 12384 KB Output is correct
10 Correct 3 ms 5224 KB Output is correct
11 Incorrect 62 ms 10080 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 3 ms 5212 KB Output is correct
2 Correct 38 ms 9376 KB Output is correct
3 Correct 55 ms 10580 KB Output is correct
4 Correct 73 ms 12372 KB Output is correct
5 Correct 61 ms 10900 KB Output is correct
6 Correct 85 ms 12384 KB Output is correct
7 Correct 79 ms 12504 KB Output is correct
8 Correct 59 ms 10592 KB Output is correct
9 Correct 82 ms 12384 KB Output is correct
10 Correct 202 ms 41312 KB Output is correct
11 Correct 324 ms 51904 KB Output is correct
12 Correct 299 ms 51788 KB Output is correct
13 Correct 241 ms 49936 KB Output is correct
14 Correct 297 ms 51664 KB Output is correct
15 Correct 305 ms 51796 KB Output is correct
16 Correct 173 ms 41196 KB Output is correct
17 Correct 285 ms 51920 KB Output is correct
18 Correct 106 ms 42580 KB Output is correct
19 Correct 101 ms 42092 KB Output is correct
20 Correct 111 ms 42320 KB Output is correct
21 Correct 96 ms 42588 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 38 ms 9376 KB Output is correct
3 Correct 55 ms 10580 KB Output is correct
4 Correct 73 ms 12372 KB Output is correct
5 Correct 61 ms 10900 KB Output is correct
6 Correct 85 ms 12384 KB Output is correct
7 Correct 79 ms 12504 KB Output is correct
8 Correct 59 ms 10592 KB Output is correct
9 Correct 82 ms 12384 KB Output is correct
10 Correct 3 ms 5224 KB Output is correct
11 Incorrect 62 ms 10080 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 38 ms 9376 KB Output is correct
3 Correct 55 ms 10580 KB Output is correct
4 Correct 73 ms 12372 KB Output is correct
5 Correct 61 ms 10900 KB Output is correct
6 Correct 85 ms 12384 KB Output is correct
7 Correct 79 ms 12504 KB Output is correct
8 Correct 59 ms 10592 KB Output is correct
9 Correct 82 ms 12384 KB Output is correct
10 Correct 3 ms 5224 KB Output is correct
11 Incorrect 62 ms 10080 KB Output isn't correct
12 Halted 0 ms 0 KB -