oj.uz

Submission #466992

# Submission time Handle Problem Language Result Execution time Memory
466992 2021-08-21T07:41:56 Z mtxas Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 5480 KB 
#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define mfsadfp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mii map<int, int>
#define all(a) a.begin(), a.end()
#define _fre() freopen("input.txt", "r", stdin)
#define turbo() cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define sz(x) ((int)x.size())
#define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
using namespace std;
#define int ll
/***********************************************************************************
                                 STRUCTS
************************************************************************************/

/***********************************************************************************
                                VARIABLES
************************************************************************************/
const int maxn = 2e5+2, inf = 1e16;
int n, q;
int c[maxn], d[maxn], r[maxn], v[maxn], s[maxn];
/***********************************************************************************
                                FUNCTIONS
************************************************************************************/
int queryStupid(int R, int V){
    int lastId = 0;
    _foreq(j, R, n){
        while(d[j] <= d[lastId]){
            j++;
            if(j == n+1) return 0;
        } // d[j] > d[lastId]
        V-= c[j];
        if(V <= 0) return j;
        lastId = j;
    }
    return 0;
}
int querySecond(int R, int V){
    int target = s[R-1] + V;
    auto it = lower_bound(s+R, s+n+3, target);
    return (it - s)%(n+1);
}
bool secondSubtask(){
    _foreq(i, 1, n-1) if(d[i] >= d[i+1]) return false;
    return true;
}
/***********************************************************************************
                                  MAIN
************************************************************************************/
signed main(){
    //_fre();
    turbo();
    cin>>n>>q;
    _foreq(i, 1, n) cin>>d[i]>>c[i];
    _for(i, 0, q) cin>>r[i]>>v[i];
    if(secondSubtask()){
        _foreq(i, 1, n) s[i] = s[i-1] + c[i];
        s[n+1] = inf;
        _for(g, 0, q) cout<<querySecond(r[g], v[g])<<'\n';
    }
    else _for(g, 0, q) cout<<queryStupid(r[g], v[g])<<'\n';

}

Compilation message

fountain.cpp: In function 'long long int queryStupid(long long int, long long int)':
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:38:5: note: in expansion of macro '_foreq'
   38 |     _foreq(j, R, n){
      |     ^~~~~~
fountain.cpp: In function 'bool secondSubtask()':
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:55:5: note: in expansion of macro '_foreq'
   55 |     _foreq(i, 1, n-1) if(d[i] >= d[i+1]) return false;
      |     ^~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:65:5: note: in expansion of macro '_foreq'
   65 |     _foreq(i, 1, n) cin>>d[i]>>c[i];
      |     ^~~~~~
fountain.cpp:17:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
fountain.cpp:66:5: note: in expansion of macro '_for'
   66 |     _for(i, 0, q) cin>>r[i]>>v[i];
      |     ^~~~
fountain.cpp:18:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
fountain.cpp:68:9: note: in expansion of macro '_foreq'
   68 |         _foreq(i, 1, n) s[i] = s[i-1] + c[i];
      |         ^~~~~~
fountain.cpp:17:31: warning: unnecessary parentheses in declaration of 'g' [-Wparentheses]
   17 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
fountain.cpp:70:9: note: in expansion of macro '_for'
   70 |         _for(g, 0, q) cout<<querySecond(r[g], v[g])<<'\n';
      |         ^~~~
fountain.cpp:17:31: warning: unnecessary parentheses in declaration of 'g' [-Wparentheses]
   17 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
fountain.cpp:72:10: note: in expansion of macro '_for'
   72 |     else _for(g, 0, q) cout<<queryStupid(r[g], v[g])<<'\n';
      |          ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5240 KB Output is correct
2 Correct 108 ms 5480 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 92 ms 5240 KB Output is correct
9 Correct 108 ms 5480 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Execution timed out 1579 ms 2948 KB Time limit exceeded
12 Halted 0 ms 0 KB -