oj.uz

Submission #137920

# Submission time Handle Problem Language Result Execution time Memory
137920 2019-07-28T14:07:12 Z mariusnicoli Plahte (COCI17_plahte) C++14
160 / 160
 1450 ms 510412 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;
};


deque<int> A[700000];
    /// 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 T[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, int 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, int 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 (T[A[nod].back()] > maxim) {
                maxim = T[A[nod].back()];
                indice = A[nod].back();
            }
        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);
            }
            T[e[i].ind] = i;
            intra(1, 1, dimY, getPoz(f[e[i].ind].y1), getPoz(f[e[i].ind].y2), e[i].ind);
        } 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);
            } else {
                /// bila
                maxim = -1;
                getLast(1, 1, dimY, getPoz(b[e[i].ind].y));
                culori[indice].insert(b[e[i].ind].c);
            }
    }

    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:107: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 739 ms 485472 KB Output is correct
2 Correct 752 ms 485972 KB Output is correct
3 Correct 481 ms 477320 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 487448 KB Output is correct
2 Correct 792 ms 486916 KB Output is correct
3 Correct 484 ms 477240 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 498144 KB Output is correct
2 Correct 1032 ms 494956 KB Output is correct
3 Correct 560 ms 477244 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 510412 KB Output is correct
2 Correct 1428 ms 507200 KB Output is correct
3 Correct 483 ms 477308 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 508816 KB Output is correct
2 Correct 1436 ms 505172 KB Output is correct
3 Correct 488 ms 477428 KB Output is correct