oj.uz

Submission #404750

# Submission time Handle Problem Language Result Execution time Memory
404750 2021-05-14T23:00:29 Z jeroenodb Plahte (COCI17_plahte) C++14
160 / 160
 752 ms 379048 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
#ifndef LOCAL
const int mxN = 8e4+1, oo = 1e9;
#else
const int mxN = 1e2+1, oo = 1e9;
#endif
unordered_set<int> colours[mxN];
int ans[mxN];
vi kid[mxN];
bitset<mxN> notroot;

void dfs(int at) {
    for(int to:kid[at]) {
        dfs(to);
        if(colours[to].size()>colours[at].size()) {
            swap(colours[at],colours[to]);
        }
        for(auto c: colours[to]) colours[at].insert(c);
    }
    ans[at] = colours[at].size();
}

struct tourtree {
    vector<stack<int>> seg;
    int ptwo = 1;
    tourtree() {}
    tourtree(int n) {
        n+=3;
        while(ptwo<n) ptwo*=2;

        seg.resize(ptwo*2);
    }
    void put(int l, int r, int i) {
        for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) {
            if(l&1) seg[l++].push(i);
            if(r&1) seg[--r].push(i);
        }
    }
    void take(int l, int r) {
        for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) {
            if(l&1) seg[l++].pop();
            if(r&1) seg[--r].pop();
        }
    }
    int get(int y) {
        int res = -1;
        for(y+=ptwo;y>0;y/=2) {
            if(!seg[y].empty()) 
                res = max(res,seg[y].top());
        }
        return res;
    }

} seg;

vi coord; // coord compression on y axis

int real(int i) {
    return lower_bound(all(coord),i)-coord.begin();
}

struct event {
    int x,y1,y2=-oo,i=-1;
    bool end = false, sheet=true;
    event() {}
    event(int X,int Y1, int Y2, int I, bool End) : x(X),y1(Y1),y2(Y2),i(I) {
        if(End) {
            coord.push_back(y1);
            coord.push_back(y2);
            end=true;
        }
    }

    bool operator<(const event& o) const {
        if(x==o.x) {
            if(sheet==o.sheet) return end<o.end;
            else if(sheet) return !end;
            else return o.end;
        }
        return x<o.x;
    }
};

int main() {
    int n,m; cin >> n >> m;
    coord.reserve(2*n+1+m); coord.push_back(oo+100);
    vector<event> es(2*n+m);
    for(int i=0;i<n;++i) {
        auto& e1 = es[2*i],&e2 = es[2*i+1];
        int a,b,c,d; cin >> a >> b >> c >> d;
        e1 = event(a,b,d,i,false);
        e2 = event(c,b,d,i,true);
    }
    for(int i=2*n;i<2*n+m;++i) {
        auto& b = es[i];
        cin >> b.x >> b.y1 >> b.i;
        b.sheet = false;
        coord.push_back(b.y1);
    }
    sort(all(coord));
    coord.erase(unique(all(coord)),coord.end());
    seg = tourtree(coord.size());
    sort(all(es));
    int level = 0;
    for(auto& e : es) {
        e.y1 = real(e.y1);
        auto getsheet = [&](int y) {
            int j = seg.get(y);
            if(j==-1) return -1;
            return es[j].i;
        };
        if(e.sheet) {
            e.y2 = real(e.y2);
            if(e.end) {
                // remove sheet from tour tree
                seg.take(e.y1,e.y2+1);
            } else {
                int par = getsheet(e.y1);
                if(par!=-1){
                    kid[par].push_back(e.i);
                    notroot[e.i] = true;
                } 
                seg.put(e.y1,e.y2+1,level);
            }
        } else {
            // shoot paintball
            int target = getsheet(e.y1);
            if(target!=-1) 
                colours[target].insert(e.i);
        }
        level++;
    }
    for(int i=0;i<n;++i) {
        if(!notroot[i]) dfs(i);
    }
    for(int i=0;i<n;++i) {
        cout << ans[i] << '\n';
    }
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 188084 KB Output is correct
2 Correct 253 ms 188952 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 189604 KB Output is correct
2 Correct 276 ms 188944 KB Output is correct
3 Correct 5 ms 6552 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 371872 KB Output is correct
2 Correct 395 ms 192520 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 379048 KB Output is correct
2 Correct 737 ms 374944 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 377340 KB Output is correct
2 Correct 752 ms 374744 KB Output is correct
3 Correct 6 ms 6604 KB Output is correct