oj.uz

Submission #466887

# Submission time Handle Problem Language Result Execution time Memory
466887 2021-08-20T23:22:47 Z TlenekWodoru Fountain (eJOI20_fountain) C++14
100 / 100
 699 ms 50112 KB 
#include <bits/stdc++.h>
using namespace std;
int srednica[100009];
int pojemnosc[100009];
vector<int>D[100009];
vector<int>D2[100009];
int V[100009][20];
long long V2[100009][20];
void DFS(int v, int poprzedni, int poprzedni_odl)
{
    int ind=poprzedni;
    long long odl=poprzedni_odl;
    for(int i=0;i<=18;i++)
    {
        V2[v][i]=odl;
        V[v][i]=ind;
        odl+=V2[ind][i];
        ind=V[ind][i];
    }
    for(int i=0;i<D[v].size();i++)
    {
        int somsiad=D[v][i];
        DFS(somsiad,v,D2[v][i]);
    }
}
int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int r,l;
        cin>>r>>l;
        srednica[i]=r;
        pojemnosc[i]=l;
    }
    map<int,int>M;
    M[1000000009]=0;
    for(int i=n;i>=1;i--)
    {
        int r=srednica[i];
        int l=pojemnosc[i];
        D[M.upper_bound(r)->second].push_back(i);
        D2[M.upper_bound(r)->second].push_back(pojemnosc[i]);
        while(M.size()>0&&M.begin()->first<=r)
        {
            M.erase(M.begin()->first);
        }
        M[r]=i;
    }
///-=-=-==-==-=-==-==-=-=-==-=-==-==-==-=-==-==-=-==-=-==-==-=-=-=
    DFS(0,0,0);
///-==-=--==-==-=-==-==--==--==-==-=-==-==-=-==-==-==-=-==-==-=-==-
    /**cout<<endl<<endl;
    for(int i=0;i<=n;i++)
    {
        cout<<endl<<"i="<<i<<"| ";
        for(int j=0;j<10;j++)
        {
            cout<<V[i][j]<<" ";
        }
    }
    cout<<endl;
    cout<<endl;
    for(int i=0;i<=n;i++)
    {
        cout<<endl<<"i="<<i<<"| ";
        for(int j=0;j<10;j++)
        {
            cout<<V2[i][j]<<" ";
        }
    }
    cout<<endl<<endl;**/
///-=-==-=-==-=-==-=-==-==-=-===-=-==-==-=-==-=-==-==--=-=
    vector<int>odp;
    for(int i=1;i<=m;i++)
    {
        int ind;
        long long k;
        cin>>ind>>k;
        for(int j=18;j>=0;j--)
        {
            if(V2[ind][j]<k)
            {
                k-=V2[ind][j];
                ind=V[ind][j];
            }
            if(ind==0){break;}
        }
        cout<<ind<<endl;
    }
    return 0;
}
/**
9 100
4 8
5 10
6 16
3 4
4 13
5 15
3 16
8 3
3 4
**/

Compilation message

fountain.cpp: In function 'void DFS(int, int, int)':
fountain.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<D[v].size();i++)
      |                 ~^~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:42:13: warning: unused variable 'l' [-Wunused-variable]
   42 |         int l=pojemnosc[i];
      |             ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 6 ms 5196 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 8 ms 5324 KB Output is correct
6 Correct 8 ms 5332 KB Output is correct
7 Correct 8 ms 5196 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 44804 KB Output is correct
2 Correct 511 ms 43840 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 6 ms 5196 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 8 ms 5324 KB Output is correct
6 Correct 8 ms 5332 KB Output is correct
7 Correct 8 ms 5196 KB Output is correct
8 Correct 465 ms 44804 KB Output is correct
9 Correct 511 ms 43840 KB Output is correct
10 Correct 8 ms 5324 KB Output is correct
11 Correct 258 ms 23616 KB Output is correct
12 Correct 699 ms 50112 KB Output is correct
13 Correct 580 ms 39352 KB Output is correct
14 Correct 498 ms 37264 KB Output is correct
15 Correct 445 ms 34624 KB Output is correct