Cod sursa(job #3364209)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 31 august 2026 14:45:14
Problema Cadrane Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

ifstream fin("cadrane.in");
ofstream fout("cadrane.out");

const int MAXN = 100000;

struct Point {
    int x, y;
} pts[MAXN];

map<int, int> mp;
int cnt;

struct SegmentTree {
    struct Node {
        int minim, lazy;
    } tree[4 * MAXN];
    int n;
    
    Node join(Node a, Node b) {
        return Node {
            min(a.minim, b.minim),
            0
        };
    }
    
    void init(int n) {
        this->n = n;
    }
    
    void addLazy(int node, int val) {
        tree[node].minim += val;
        tree[node].lazy += val;
    }
    
    void propagate(int node) {
        if(tree[node].lazy != 0) {
            addLazy(2 * node, tree[node].lazy);
            addLazy(2 * node + 1, tree[node].lazy);
            tree[node].lazy = 0;
        }
    }
    
    void update(int node, int left, int right, int qleft, int qright, int val) {
        if(qleft <= left && right <= qright) {
            addLazy(node, val);
        } else {
            propagate(node);
            int middle = (left + right) / 2;
            if(qleft <= middle) {
                update(2 * node, left, middle, qleft, qright, val);
            }
            if(middle < qright) {
                update(2 * node + 1, middle + 1, right, qleft, qright, val);
            }
            tree[node] = join(tree[2 * node], tree[2 * node + 1]);
        }
    }
    
    void update(int st, int dr, int val) {
        if(st <= dr) {
            update(1, 1, n, st, dr, val);
        }
    }
    
    int query(int node, int left, int right, int qleft, int qright) {
        if(qleft <= left && right <= qright) {
            return tree[node].minim;
        }
        propagate(node);
        int middle = (left + right) / 2, answer = 1e9;
        if(qleft <= middle) {
            answer = min(answer, query(2 * node, left, middle, qleft, qright));
        }
        if(middle < qright) {
            answer = min(answer, query(2 * node + 1, middle + 1, right, qleft, qright));
        }
        return answer;
    }
    
    int query(int st, int dr) {
        return query(1, 1, n, st, dr);
    }
} aint;

int main() {
    int n;
    fin >> n;
    for(int i = 0; i < n; i++) {
        fin >> pts[i].x >> pts[i].y;
        mp[pts[i].x] = mp[pts[i].y] = 1;
    }
    
    for(auto &it : mp) {
        it.second = ++cnt;
    }
    
    for(int i = 0; i < n; i++) {
        pts[i].y = mp[pts[i].y];
    }
    sort(pts, pts + n, [&](Point a, Point b) {
        return a.x < b.x;
    });
    
    aint.init(cnt);
    for(int i = 0; i < n; i++) {
        aint.update(1, pts[i].y, +1);
    }
    
    int answer = 0;
    for(int i = 0; i < n; i++) {
        int j = i;
        while(j < n && pts[i].x == pts[j].x) {
            j++;
        }
        for(int q = i; q < j; q++) {
            aint.update(pts[q].y + 1, cnt, +1);
        }
        answer = max(answer, aint.query(1, cnt));
        for(int q = i; q < j; q++) {
            aint.update(1, pts[q].y - 1, -1);
        }
        i = j - 1;
    }
    fout << answer << "\n";
    return 0;
}