oj.uz

Submission #886109

# Submission time Handle Problem Language Result Execution time Memory
886109 2023-12-11T13:21:32 Z Zero_OP Plahte (COCI17_plahte) C++14
160 / 160
 241 ms 39416 KB 
#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct point{
    int x, y;
    point(int x = 0, int y = 0) : x(x), y(y) {}

    friend istream& operator >> (istream& in, point& p){
        return in >> p.x >> p.y;
    }
};

struct rectangle{
    point upper, lower;
};

struct event{
    int t, type, id;
    bool operator < (const event& o){
        return make_tuple(t, type, id) < make_tuple(o.t, o.type, o.id);
    }
};

const int N = 8e4 + 5;

int n, q, tin[N], tout[N], paintColor[N], st[N << 4], lzy[N << 4], res[N], par[N];
rectangle r[N];
point p[N];
vector<int> adj[N];
set<int> clr[N];

void apply(int id, int val){
    st[id] = val;
    lzy[id] = val;
}

void pushDown(int id){
    if(lzy[id] != -1){
        apply(id << 1, lzy[id]);
        apply(id << 1 | 1, lzy[id]);
        lzy[id] = -1;
    }
}

void update(int id, int l, int r, int u, int v, int val){
    if(v < l or u > r) return;
    if(u <= l and r <= v){
        apply(id, val);
    }
    else{
        int mid = l + r >> 1;
        pushDown(id);
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);

        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
}

int query(int id, int l, int r, int u, int v){
    if(v < l or u > r) return -1;
    if(u <= l and r <= v) return st[id];
    int mid = l + r >> 1;
    pushDown(id);
    return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
}

void dfs(int u){
    for(int v : adj[u]){
        dfs(v);
        if(clr[u].size() < clr[v].size()) swap(clr[u], clr[v]);
        for(int val : clr[v]) clr[u].insert(val);
    }

    res[u] = (clr[u].size());
}

void sweepLine(){
    vector<int> coordY;

    vector<event> events;
    for(int i = 1; i <= n; ++i){
        coordY.push_back(r[i].lower.y);
        coordY.push_back(r[i].upper.y);
        events.push_back({r[i].lower.x, -1, i});
        events.push_back({r[i].upper.x, +1, i});
    }
    for(int i = 1; i <= q; ++i){
        coordY.push_back(p[i].y);
        events.push_back({p[i].x, 0, i});
    }

    sort(range(coordY));
    compact(coordY);

    memset(lzy, -1, sizeof(lzy));

    for(int i = 1; i <= n; ++i){
        r[i].lower.y = lower_bound(range(coordY), r[i].lower.y) - coordY.begin() + 1;
        r[i].upper.y = lower_bound(range(coordY), r[i].upper.y) - coordY.begin() + 1;
    }

    for(int i = 1; i <= q; ++i){
        p[i].y = lower_bound(range(coordY), p[i].y) - coordY.begin() + 1;
    }

    sort(range(events));

    int lb = 1, ub = coordY.size();
    for(int i = 0; i < events.size(); ++i){
        int x = events[i].t, type = events[i].type, id = events[i].id;
        //cout << x << ' ' << type << ' ' << id << '\n';
        if(type == -1){
            //add
            int L = r[id].lower.y, R = r[id].upper.y;
            par[id] = query(1, lb, ub, L, R);
            update(1, lb, ub, L, R, id);
        }
        else if(type == 0){
            //query
            int u = query(1, lb, ub, p[id].y, p[id].y);
            if(u > 0){
                clr[u].insert(paintColor[id]);
            }
        }
        else{
            //delete
            int L = r[id].lower.y, R = r[id].upper.y;
            update(1, lb, ub, L, R, par[id]);
        }
    }

    vector<int> roots;
    for(int i = 1; i <= n; ++i){
        if(!par[i]){
            roots.push_back(i);
        }
        else adj[par[i]].push_back(i);
    }

    for(int u : roots) dfs(u);

    for(int i = 1; i <= n; ++i){
        cout << res[i] << '\n';
    }
}

void Zero_OP(){
    cin >> n >> q;

    for(int i = 1; i <= n; ++i){
        cin >> r[i].lower >> r[i].upper;
    }
    for(int i = 1; i <= q; ++i){
        cin >> p[i] >> paintColor[i];
    }

    sweepLine();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    Zero_OP();

    return 0;
}

Compilation message

plahte.cpp: In function 'void update(int, int, int, int, int, int)':
plahte.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
plahte.cpp: In function 'int query(int, int, int, int, int)':
plahte.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = l + r >> 1;
      |               ~~^~~
plahte.cpp: In function 'void sweepLine()':
plahte.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 0; i < events.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
plahte.cpp:129:13: warning: unused variable 'x' [-Wunused-variable]
  129 |         int x = events[i].t, type = events[i].type, id = events[i].id;
      |             ^
plahte.cpp: In function 'int main()':
plahte.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 22748 KB Output is correct
2 Correct 79 ms 23436 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 24340 KB Output is correct
2 Correct 82 ms 23420 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 33496 KB Output is correct
2 Correct 137 ms 27092 KB Output is correct
3 Correct 3 ms 17240 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 39416 KB Output is correct
2 Correct 233 ms 34796 KB Output is correct
3 Correct 3 ms 17004 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 37004 KB Output is correct
2 Correct 226 ms 34260 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct