oj.uz

Submission #137898

# Submission time Handle Problem Language Result Execution time Memory
137898 2019-07-28T13:31:23 Z mariusnicoli Plahte (COCI17_plahte) C++14
64 / 160
 1411 ms 524288 KB 
#include <fstream>
#include <iostream>
#include <deque>
#include <set>
#include <vector>
#include <algorithm>
#define INF 1000000001
using namespace std;
///ifstream cin("plahte.in");
///ofstream cout("plahte.out");
struct foaie {
    int x1;
    int y1;
    int x2;
    int y2;
};
struct bila {
    int x;
    int y;
    int c;
};
struct eveniment {
    int tip; /// 1 incepe dreptunghi, 2 bila, 3 se termina dreptunghi
    int x;
    int ind;
};

struct moment {
    int indDr;
    int timp;
};

deque<moment> A[500000];
    /// coada cu indice de
    /// evenimente, de unde obtin dreptunghiul

foaie f[80001];
bila b[80001];
eveniment e[240001];
set <int> culori[80010];
vector <int> L[80010];
int Y[240001];
int dimY, maxim, indice, n, m, k;
int sol[80010];
int cmp (const eveniment &a, const eveniment &b) {
    if (a.x != b.x)
        return a.x < b.x;
    else
        return a.tip < b.tip;
}

void intra(int nod, int st, int dr, int a, int b, moment m)  {
    if (a <= st && dr <= b) {
        A[nod].push_back(m);
    } else {
        int mid = (st + dr)/2;
        if (a <= mid)
            intra(2*nod, st, mid, a, b, m);
        if (b > mid)
            intra(2*nod+1, mid+1, dr, a, b, m);
    }
}

void iese(int nod, int st, int dr, int a, int b, moment m)  {
    if (a <= st && dr <= b) {
        A[nod].pop_back();
    } else {
        int mid = (st + dr)/2;
        if (a <= mid)
            iese(2*nod, st, mid, a, b, m);
        if (b > mid)
            iese(2*nod+1, mid+1, dr, a, b, m);
    }
}
set<int> ally;

int getPoz(int y) {
    int st = 1,dr = dimY;
    while (st <= dr) {
        int mid = (st+dr)/2;
        if (Y[mid] == y)
            return mid;
        if (Y[mid] > y)
            dr = mid-1;
        else
            st = mid+1;
    }
    return -1;
}

void getLast(int nod, int st, int dr, int y) {
    if (st <= dr) {
        if (A[nod].size())
            if (A[nod].back().timp > maxim) {
                maxim = A[nod].back().timp;
                indice = A[nod].back().indDr;
            }
        if (st == dr)
            return;
        int mid = (st + dr)/2;
        if (y <= mid)
            getLast(2*nod, st, mid, y);
        else
            getLast(2*nod+1, mid+1, dr, y);
    }
}

void dfs(int nod) {
    int poz = nod;
    for (int i=0;i<L[nod].size();i++) {
        int vecin = L[nod][i];
        dfs(vecin);
        if (culori[poz].size() < culori[vecin].size()) {
            swap(poz, vecin);

        }
        for(set<int>::iterator it = culori[vecin].begin(); it != culori[vecin].end(); it++) {
            culori[poz].insert(*it);
        }
    }
    sol[nod] = culori[poz].size();
    swap(culori[nod], culori[poz]);
}

int main () {
    cin>>n>>m;

    for (int i=0;i<=n;i++) {
        if (i == 0) {
            f[i].x1 = -INF;
            f[i].y1 = -INF;
            f[i].x2 = INF;
            f[i].y2 = INF;
        } else
            cin>>f[i].x1>>f[i].y1>>f[i].x2>>f[i].y2;
        ally.insert(f[i].y1);
        ally.insert(f[i].y2);
        k++;
        e[k].tip = 1;
        e[k].x = f[i].x1;
        e[k].ind = i;
        k++;
        e[k].tip = 3;
        e[k].x = f[i].x2;
        e[k].ind = i;
    }
    for (int i=1;i<=m;i++) {
        cin>>b[i].x>>b[i].y>>b[i].c;
        ally.insert(b[i].y);
        k++;
        e[k].tip = 2;
        e[k].x = b[i].x;
        e[k].ind = i;
    }

    sort(e+1, e+k+1, cmp);

    for (set<int>::iterator it = ally.begin(); it != ally.end(); it++)
        Y[++dimY] = *it;

    for (int i=1;i<=k;i++) {
        if (e[i].tip == 1) {
            /// intra dreptunghi
            if (e[i].x != -INF) {
                maxim = -1;
                getLast(1, 1, dimY, getPoz(f[e[i].ind].y1));
                ///T[e[i].ind] = indice;
                L[indice].push_back(e[i].ind);
            }
            intra(1, 1, dimY, getPoz(f[e[i].ind].y1), getPoz(f[e[i].ind].y2), {e[i].ind, i});
        } else
            if (e[i].tip == 3) {
                iese(1, 1, dimY, getPoz(f[e[i].ind].y1), getPoz(f[e[i].ind].y2), {e[i].ind, i});
            } else {
                /// bila
                maxim = -1;
                getLast(1, 1, dimY, getPoz(b[e[i].ind].y));
                culori[indice].insert(b[e[i].ind].c);
            }
    }

    /// avem un vector de
    /**
    cout<<"\n";
    for(vector <int>::iterator it = L[0].begin(); it != L[0].end(); it++)
        cout<<*it<<"\n";
    cout<<L[0].size()<<" "<<L[1].size()<<" "<<L[2].size();
    **/
/**
    for (int i=0;i<=n;i++)
        cout<<culori[i].size()<<"\n";
**/

    dfs(0);
    for (int i=1;i<=n;i++)
        cout<<sol[i]<<"\n";
    return 0;
}

Compilation message

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++) {
                  ~^~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 350776 KB Output is correct
2 Correct 609 ms 351132 KB Output is correct
3 Correct 344 ms 342648 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 352540 KB Output is correct
2 Correct 689 ms 351744 KB Output is correct
3 Correct 347 ms 342624 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1139 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1411 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1404 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -