oj.uz

Submission #404746

# Submission time Handle Problem Language Result Execution time Memory
404746 2021-05-14T22:39:21 Z jeroenodb Plahte (COCI17_plahte) C++14
128 / 160
 725 ms 381748 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 = 1e5+1, oo = 1e9, ptwo = 1<<18;
#else
const int mxN = 1e2+1, oo = 1e9, ptwo = 1<<8;
#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 {
    stack<int> seg[2*ptwo];
    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;
    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+2); coord.push_back(oo+100); coord.push_back(-1);
    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());
    sort(all(es));
    int level = 0;
    for(auto& e : es) {

        auto getsheet = [&](int y) {
            int j = seg.get(y);
            if(j==-1) return -1;
            return es[j].i;
        };
        if(e.sheet) {
            e.y1 = real(e.y1);
            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 realy = real(e.y1),target=-1;
            if(coord[realy]==e.y1) target = getsheet(realy);
            else {
                // paintball coordinate is in between compressed sheet coordinates
                target = getsheet(realy);
                int t2 = getsheet(realy-1);
                if(target!=t2) target = -1;
            }
            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 396 ms 367256 KB Output is correct
2 Correct 385 ms 368036 KB Output is correct
3 Correct 245 ms 360996 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 368812 KB Output is correct
2 Correct 431 ms 368200 KB Output is correct
3 Correct 246 ms 361092 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 374664 KB Output is correct
2 Correct 530 ms 371088 KB Output is correct
3 Correct 242 ms 361028 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 381748 KB Output is correct
2 Correct 724 ms 377028 KB Output is correct
3 Incorrect 245 ms 361056 KB Output isn't correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 379892 KB Output is correct
2 Correct 702 ms 376920 KB Output is correct
3 Correct 247 ms 361068 KB Output is correct