Submission #1000061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000061		daffuwu	Global Warming (CEOI18_glo)	C++14	100 / 100	359 ms	41668 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, x, t[200069], ans, dp[2], a, b;
vector<int> comp;

struct node
{
    int l, r, val;
    node *le, *ri;
    void bd(int cl, int cr)
    {
        l = cl;
        r = cr;
        if (l == r) val = 0;
        else 
        {
            int md = (l+r)/2;
            le = new node();
            ri = new node();
            le->bd(l, md);
            ri->bd(md+1, r);
            val = 0;
        } 
    }
    void upd(int idx, int x)
    {
        if (l>idx || r<idx) return;
        if (l == r)
        {
            val = max(val, x);
            return;
        }
        le->upd(idx, x);
        ri->upd(idx, x);
        val = max(le->val, ri->val);
    }
    int qry(int ql, int qr)
    {
        if (l>qr || r<ql) return 0;
        if (ql<=l && r<=qr) return val;
        return max(le->qry(ql, qr), ri->qry(ql, qr));
    }
} *rt[2];

int main() 
{
    int i, j;
    scanf("%d%d", &n, &x);
    rt[0] = new node();
    rt[1] = new node();
    rt[0]->bd(1, n+1);
    rt[1]->bd(1, n+1);
    comp.push_back(0);
    for (i=1; i<=n; i++)
    {
        scanf("%d", t+i);
        comp.push_back(t[i]);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end())-comp.begin());
    for (i=1; i<=n; i++)
    {
        a = lower_bound(comp.begin(), comp.end(), t[i])-comp.begin()+1;
        b = lower_bound(comp.begin(), comp.end(), t[i]+x)-comp.begin()+1;
        dp[0] = 1+rt[0]->qry(1, a-1);
        dp[1] = 1+max(rt[0]->qry(1, b-1), rt[1]->qry(1, a-1));
        rt[0]->upd(a, dp[0]);
        rt[1]->upd(a, dp[1]);
        ans = max(ans, dp[1]);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:51:12: warning: unused variable 'j' [-Wunused-variable]
   51 |     int i, j;
      |            ^
glo.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d", &n, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d", t+i);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25