Submission #1555044

---

Source Code Expand

#include <cstdio>
#include <cctype>
#include <algorithm>

namespace Zeonfai
{
    inline int getInt()
    {
        int a = 0, sgn = 1; char c;
        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
        while(isdigit(c)) a =  a * 10 + c - '0', c = getchar();
        return a * sgn;
    }
}
using namespace std;
const int N = (int)2e5, INF = (int)1e9;
int n;
int mn[N], mx[N];
struct point
{
    int v, pos;
    inline int operator <(const point &a) const {return v < a.v;}
}p[N];
struct section
{
    int L, R;
    inline int operator <(const section &a) const {return R < a.R;}
}sec[N];
struct segmentTree
{
    struct node
    {
        node *suc[2];
        long long sum;
        inline node() {for(int i = 0; i < 2; ++ i) suc[i] = NULL;}
    }*rt;
    inline segmentTree() {rt = NULL;}
    node* modify(node *u, int L, int R, int pos, long long x)
    {
        if(u == NULL) u = new node;
        u->sum += x;
        if(L == R) return u;
        if(pos <= L + R >> 1) u->suc[0] = modify(u->suc[0], L, L + R >> 1, pos, x); else u->suc[1] = modify(u->suc[1], (L + R >> 1) + 1, R, pos, x);
        return u;
    }
    inline void modify(int pos, long long x) {rt = modify(rt, 0, INF, pos, x);}
    long long query(node *u, int curL, int curR, int L, int R)
    {
        if(u == NULL) return 0;
        int mid = curL + curR >> 1; long long res = 0;
        if(L <= mid) res += query(u->suc[0], curL, mid, L, R);
        if(R > mid) res += query(u->suc[1], mid + 1, curR, L, R);
        return res;
    }
    inline long long query(int L, int R) {return query(rt, 0, INF, L, R);}
}seg;
struct binaryIndexedTree
{
    long long a[N + 2];
    inline void modify(int pos, int x)
    {
        for(int i = pos + 1; i <= n + 1; i += i & - i) a[i] += x;
    }
    long long query(int pos)
    {
        long long res = 0;
        for(int i = pos + 1; i; i -= i & - i) res += a[i];
        return res;
    }
    inline long long query(int L, int R) {return query(R) - query(L - 1);}
}BIT;
int main()
{


    using namespace Zeonfai;
    n = getInt();
    for(int i = 1; i <= n; ++ i) p[i].pos = getInt(), p[i].v = getInt(), seg.modify(p[i].pos, p[i].v);
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; ++ i) mx[i] = i == 1 ? p[i].pos : max(mx[i - 1], p[i].pos);
    for(int i = n; i; -- i) mn[i] = i == n ? p[i].pos : min(mn[i + 1], p[i].pos);
    for(int i = 1; i <= n; ++ i)
    {
        int L = 1, R = i - 1, pos = i;
        while(L <= R) if(mx[L + R >> 1] > p[i].pos) {pos = L + R >> 1; R = (L + R >> 1) - 1;} else L = (L + R >> 1) + 1;
        sec[i].L = pos;
        L = i + 1; R = n; pos = i;
        while(L <= R) if(mn[L + R >> 1] < p[i].pos) {pos = L + R >> 1; L = (L + R >> 1) + 1;} else R = (L + R >> 1) - 1;
        sec[i].R = pos;
    }
    sort(sec, sec + n);
    BIT.modify(0, 1);
    for(int i = 1; i <= n; ++ i)
        BIT.modify(sec[i].R, BIT.query(sec[i].L - 1, sec[i].R));
    printf("%lld\n", BIT.query(n, n));
}

Submission Info

Judge Result