//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int N = 500001;
using namespace std;
ll n, m, t[800001], dp[200001], a, b;
pair <ll, ll> p[200001];
ll gcd (ll a, ll b){while (a > 0 && b > 0){if (a >= b){a %= b;}else{b %= a;}}return a + b;}
ll binpow (ll a, ll b){
a %= mod;if (b == 0){return 1;}
else if (b % 2 == 1){
return binpow (a, b - 1) % mod * a % mod;
}
else{
ll t = binpow (a, b / 2) % mod;
return t * t % mod;
}
}
void build (ll tl = 1, ll tr = n, ll v = 1){
if (tl == tr){
t[v] = p[tl].F;
return;
}
ll tm = (tl + tr) / 2;
build (tl, tm, v * 2);
build (tm + 1, tr, v * 2 + 1);
t[v] = max (t[v * 2], t[v * 2 + 1]);
}
ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
if (r < tl || tr < l){
return 0;
}
if (l <= tl && tr <= r){
return t[v];
}
ll tm = (tl + tr) / 2;
return max (get (l, r, tl, tm, v * 2), get (l, r, tm + 1, tr, v * 2 + 1));
}
void Jemirlan(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> p[i].F >> p[i].S;
}
build ();
dp[n] = p[n].S;
for (int i = n - 1; i >= 1; i--){
ll l = i + 1, r = n;
while (l <= r){
ll md = (l + r) / 2;
if (get (i + 1, md) > p[i].F){
r = md - 1;
}
else{
l = md + 1;
}
}
dp[i] = p[i].S;
if (l <= n){
dp[i] += dp[l];
}
}
for (int i = 1; i <= n; i++){
cout << dp[i] << ' ';
}
while (m--){
cin >> a >> b;
if (dp[a] < b){
cout << "0\n";
}
else{
cout << "blmim\n";
}
}
}
signed main (/*JALEM*/){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll tt = 1;
// cin >> tt;
for (int i = 1; i <= tt; i++){
// cout << "Case " << i << ": ";
Jemirlan();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
