oj.uz

답안 #548457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548457 2022-04-13T13:07:40 Z shmad Fountain (eJOI20_fountain) C++17
30 / 100
 63 ms 3260 KB 
#include <bits/stdc++.h>
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")

#define pb push_back
#define pob pop_back
#define ll long long
#define ld long double
#define int ll // HERE CAN BE WA/RE/MLE/TLE
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) s.size()
#define skip continue
#define y0 ijl
#define y1 hjk
#define equal bayan
#define friend trs
#define delete bae
#define div aber
#define exp earb
#define new heiu
#define t1 sgher
#define t0 sorei

using namespace std;

const int N = 1e6 + 7;
const int K = 1e7 + 7;
const int WN = 1e7 + 7;
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-6;



int p[N];
void solve() {
    int n, q;
    cin >> n >> q;
    vector <pair <int, int>> v(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> v[i].x >> v[i].y;
        p[i] = p[i - 1] + v[i].y;
    }
    //for (int i = 1;i <= n;i++)cout << p[i] << ' ';
    if (n <= 1000 && q <= 2000) {
        while (q--) {
            int pos, sum;
            cin >> pos >> sum;
            int last = v[pos].x;
            sum -= v[pos].y;
            if (sum <= 0) {
                cout << pos << '\n';
                skip;
            }
            for (int i = pos + 1;i <= n;i++) {
                if (v[i].x > last) {
                    sum -= v[i].y;
                    if (sum <= 0) {
                        cout << i << '\n';
                        break;
                    }
                    last = v[i].x;
                }
            }
            if (sum > 0) {
                cout << 0 << '\n';
                skip;
            }
        }
        return;
    }else {
        while (q--) {
            int pos, sum;
            cin >> pos >> sum;
            int l = 1, r = n, ans = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (p[mid] - p[pos - 1] < sum)l = mid + 1, ans = mid;
                else r = mid - 1;
            }
            cout << ans << '\n';
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("Hardproblem.in", "r", stdin);
    //freopen("Hardproblem.out", "w", stdout);
    int t;
    t = 1;
    //cin >> t;
    for (int i = 1;i <= t;i++) {
        //cout << i << ':';
        solve();
    }
  return 0;
}

Compilation message

fountain.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("g",on)
      | 
fountain.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 3260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 63 ms 3260 KB Output isn't correct
9 Halted 0 ms 0 KB -