oj.uz

Submission #1020279

# Submission time Handle Problem Language Result Execution time Memory
1020279 2024-07-11T19:21:02 Z FIFI_cpp Fountain (eJOI20_fountain) C++17
30 / 100
 1500 ms 12104 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<pair<int,int>,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
//ifstream fin ("sleepy.in");
//ofstream fout ("sleepy.out");
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
const int INF = 10000000000000000;
const int mod = 1000000007;
int32_t main() {
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> a(n,{-1,-1});
    for (int i = 0;i < n;i++)
    {
        cin >> a[i].first >> a[i].second;//diameter,volume
    }
    vector<vector<pair<int,int>>> query;//query number,v
    query.resize(n);
    vector<int> res(q,0);
    for (int i = 0;i < q;i++)
    {
        int r,v;
        cin >> r >> v;
        r--;
        query[r].pb({i,v});
    }
    stack<ppi> st;//quantity,radius,query
    for (int i = 0;i < n;i++)
    {
        stack<ppi> curr;
        while (!st.empty() && a[i].first > st.top().first.second)
        {
            int q = st.top().first.first;
            int r = st.top().first.second;
            int qu = st.top().second;
            if (q - a[i].second > 0)
            {
                curr.push({{q - a[i].second,a[i].first},qu});
            }
            else
            {
                res[qu] = i + 1;
            }
            st.pop();
        }
        while (!curr.empty())
        {
            st.push(curr.top());
            curr.pop();
        }
        for (int j = 0;j < query[i].size();j++)
        {
            if (a[i].second >= query[i][j].second)
            {
                res[query[i][j].first] = i + 1;
            }
            else
            {
                st.push({{query[i][j].second - a[i].second,a[i].first},query[i][j].first});
            }
        }
    }
    for (int i = 0;i < q;i++)
    {
        cout << res[i] << '\n';
    }
    return 0;
}

Compilation message

fountain.cpp:32:9: warning: "/*" within comment [-Wcomment]
   32 | /*   /\_/\
      |          
fountain.cpp: In function 'int32_t main()':
fountain.cpp:64:17: warning: unused variable 'r' [-Wunused-variable]
   64 |             int r = st.top().first.second;
      |                 ^
fountain.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j = 0;j < query[i].size();j++)
      |                        ~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1550 ms 12104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1550 ms 12104 KB Time limit exceeded
9 Halted 0 ms 0 KB -