Submission #49545573

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

i64 n, aa[N];

int fr[11]{0}, bk[11][N]{0};

 
struct cover_tree {
    struct node {
        int min;
        int min_length;
        int lazy;
        int64_t length;
 
        node() {
            lazy = min = min_length = 0;
        }
    };
 
    std::vector<node> t;
    std::vector<int> *intervals;
 
    void build(int v, int l, int r) {
        if (l == r) {
            if (l < intervals->size())
                t[v].min_length = t[v].length = (*intervals)[l];
        } else {
            build(2*v+1, l, (l+r)/2); build(2*v+2, (l+r)/2+1, r);
            t[v].length = t[2*v+1].length + t[2*v+2].length;
            t[v].min_length = t[2*v+1].min_length + t[2*v+2].min_length;
        }
    }
 
    cover_tree(std::vector<int> &intervals) {
        this->intervals = &intervals;
        t.resize(N<<2);
        build(0, 0, N-1);
    }
 
    void push(int v, int l, int r) {
        if (!t[v].lazy) return;
        t[v].min += t[v].lazy;
        if (l != r) t[2*v+1].lazy += t[v].lazy, t[2*v+2].lazy += t[v].lazy;
        t[v].lazy = 0;
    }
 
    void update(int x, int y, int k) {
        return update(0, 0, N-1, x, y, k);
    }
 
    void update(int v, int l, int r, int x, int y, int k) {
        push(v, l, r);
        if (y < l || r < x) return;
        if (x <= l && r <= y) {
            t[v].lazy += k;
            push(v, l, r);
            return;
        }
        update(2*v+1, l, (l+r)/2, x, y, k);
        update(2*v+2, (l+r)/2+1, r, x, y, k);
        t[v].min = std::min(t[2*v+1].min, t[2*v+2].min);
        t[v].min_length = (t[v].min == t[2*v+1].min ? t[2*v+1].min_length : 0) + (t[v].min == t[2*v+2].min ? t[2*v+2].min_length : 0);
    }
 
    int64_t covered() {
        return t[0].length - (t[0].min == 0 ? t[0].min_length : 0);
    }
};
 
struct Rect {
    int x1, y1, x2, y2;
};
vector<Rect> a;
 
struct Event {
    int position;
    int type;
    int index;
    bool operator<(const Event &o) const {
        if (position != o.position) return position < o.position;
        if (type != o.type) return type < o.type;
        return index < o.index;
    }
};
 
std::vector<int> y_cord;
std::vector<int> y_intervals;
std::vector<Event> evnts;
int m;
 
int64_t answer = 0;

void area()
{
    if(!m)return;
    for (int i = 0; i < m; ++i) {
        evnts.push_back(Event{a[i].x1, 1, i});
        evnts.push_back(Event{a[i].x2, -1, i});
        y_cord.push_back(a[i].y1);
        y_cord.push_back(a[i].y2);
    }
    std::sort(y_cord.begin(), y_cord.end());
    y_cord.resize(std::unique(y_cord.begin(), y_cord.end()) - y_cord.begin());
    for (size_t i = 1; i < y_cord.size(); ++i) y_intervals.push_back(y_cord[i] - y_cord[i-1]);
    std::sort(evnts.begin(), evnts.end());
 
    cover_tree cver(y_intervals);
 
    int64_t last_x = evnts[0].position;
    for (std::vector<Event>::iterator it = evnts.begin(); it != evnts.end(); ++it) {
        Rect *r = a.data() + it->index;
        answer += (it->position - last_x) * cver.covered();
        int low_ = std::lower_bound(y_cord.begin(), y_cord.end(), r->y1) - y_cord.begin();
        int high_ = std::lower_bound(y_cord.begin(), y_cord.end(), r->y2) - y_cord.begin() - 1;
        cver.update(low_, high_, it->type);
        last_x = it->position;
    }
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> aa[i];
    

    for (int i = 1; i <= 10; ++i) 
    {
        bk[i][n+1] = n+1;
        for (int j = n; j >= 1; --j)
        {
            bk[i][j] = bk[i][j+1];
            if (aa[j] == i) bk[i][j] = j;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int k = 1; k <= 10; ++k)
        {
            int p = aa[i] * 2 - k;
            if (p > 10 or p < 1) continue;
            int l = fr[k], r = bk[p][i+1];
            if (l >= 1 and r <= n)
                a.emplace_back(Rect{0, r, l, int(n)+1});
        }
        fr[aa[i]] = i;
    }
    m = a.size();

    area();
    cout << answer;
    return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void cover_tree::build(int, int, int)’:
Main.cpp:50:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   50 |             if (l < intervals->size())
      |                 ~~^~~~~~~~~~~~~~~~~~~

Judge Result