Submission #1121176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121176		FIFI_cpp	Bouquet (EGOI24_bouquet)	C++17	0 / 100	3088 ms	20932 KiB

Main

#include <bits/stdc++.h>
#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>
#include <numeric>

#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
//#define int int64_t

using namespace std;
//    /\_/\
//   (= ._.)
//   / >  \>
// encouraging cat
const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
int t[4 * MAXN];
struct Tulip {
    int pos, l, r;
};
void build(vector<int> a, int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
int mx(int v, int tl, int tr, int l, int r) {
    if (l < 0 || r < 0)
        return 0;
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return max(mx(v*2, tl, tm, l, min(r, tm)), mx(v*2+1, tm+1, tr, max(l, tm+1), r));
}
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = max(new_val, t[v]);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
bool cmp(const Tulip &x, const Tulip &y) {
    if (x.r == y.r)
        return x.pos > y.pos; 
    return x.r < y.r;
}
signed main()
{
    int n;
    cin >> n;
    vector<Tulip> tulip(n);
    for (int i = 0;i < n;i++)
    {
        cin >> tulip[i].l >> tulip[i].r;
        tulip[i].l = max(i - tulip[i].l, 0);
        tulip[i].r = min(i + tulip[i].r, n - 1);
        tulip[i].pos = i;
    }
    sort(all(tulip), cmp);
    vector<int> res(n,0);

    build(res,1,0,n - 1);
    for (int i = 0;i < n;i++)
    {
        res[i] = mx(1, 0,n - 1, 0, tulip[i].l - 1) + 1;
        update(1, 0, n - 1, tulip[i].pos, res[i]);
    }
    int ans = 0;
    for (int i = 0;i < n;i++)
    {
        ans = max(res[i], ans);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp:32:1: warning: multi-line comment [-Wcomment]
   32 | //    /\_/\
      | ^
Main.cpp:36:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   36 | const int INF = 10000000000000000;
      |                 ^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 16
• Subtask 3: 0 / 28
• Subtask 4: 0 / 18
• Subtask 5: 0 / 30