oj.uz

Submission #498186

# Submission time Handle Problem Language Result Execution time Memory
498186 2021-12-24T14:33:50 Z Karabasan Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 15576 KB 
#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse4,sse2,avx")
#pragma GCC optimize("unroll-loops")
 
int n,m,k,q;
int d[100005];
int c[100005];
int pre[100005];
vector<pair<int,int> > p[200005];
int mark[100005];
int nextt[100005];
int cevap[200005];
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>d[i]>>c[i];
    for(int i=1;i<=q;i++)
    {
        int a,b;
        cin>>a>>b;
        p[a].push_back({b,i});
    }
    stack<int> st;
    st.push(1);
    for(int i=2;i<=n;i++)
    {
        while(!st.empty()&&d[st.top()]<d[i])
        {
            nextt[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    for(int u=1;u<=n;u++)
    {
        vector<int> v;
        vector<int> ind;
        if(mark[u])
            continue;
        v.push_back(0);
        v.push_back(c[u]);
        ind.push_back(0);
        ind.push_back(u);
        int g=nextt[u];
        while(g!=0)
        {
            ind.push_back(g);
            v.push_back(v[v.size()-1]+c[g]);
            g=nextt[g];
        }
        for(int i=1;i<ind.size();i++)
        {
            if(mark[ind[i]])
                continue;
            mark[ind[i]]=1;
            for(int j=0;j<p[ind[i]].size();j++)
            {
                int a=ind[lower_bound(v.begin()+i,v.end(),p[ind[i]][j].first+v[i-1])-v.begin()];
                if(a<=n)
                    cevap[p[ind[i]][j].second]=a;
                else cevap[p[ind[i]][j].second]=0;
            }
        }
    }
    for(int i=1;i<=q;i++)
        cout<<cevap[i]<<endl;
}
signed main()
{
    fast1
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=1;i<ind.size();i++)
      |                     ~^~~~~~~~~~~
fountain.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int j=0;j<p[ind[i]].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 4 ms 5032 KB Output is correct
4 Correct 4 ms 5036 KB Output is correct
5 Correct 5 ms 5032 KB Output is correct
6 Correct 5 ms 5028 KB Output is correct
7 Correct 4 ms 5036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9732 KB Output is correct
2 Correct 83 ms 10508 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 4 ms 5032 KB Output is correct
4 Correct 4 ms 5036 KB Output is correct
5 Correct 5 ms 5032 KB Output is correct
6 Correct 5 ms 5028 KB Output is correct
7 Correct 4 ms 5036 KB Output is correct
8 Correct 73 ms 9732 KB Output is correct
9 Correct 83 ms 10508 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 1022 ms 9128 KB Output is correct
12 Correct 112 ms 15576 KB Output is correct
13 Execution timed out 1551 ms 15352 KB Time limit exceeded
14 Halted 0 ms 0 KB -