oj.uz

답안 #137922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137922 2019-07-28T14:11:32 Z mariusnicoli Plahte (COCI17_plahte) C++14
160 / 160
 1454 ms 505564 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 DREPTUNGHIURI
 
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:106: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

# 결과 실행 시간 메모리 Grader output
1 Correct 750 ms 485692 KB Output is correct
2 Correct 754 ms 486252 KB Output is correct
3 Correct 496 ms 477256 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 804 ms 487656 KB Output is correct
2 Correct 801 ms 486608 KB Output is correct
3 Correct 487 ms 477304 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1065 ms 495120 KB Output is correct
2 Correct 1057 ms 491896 KB Output is correct
3 Correct 483 ms 477304 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1437 ms 505564 KB Output is correct
2 Correct 1425 ms 502312 KB Output is correct
3 Correct 489 ms 477236 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1454 ms 504236 KB Output is correct
2 Correct 1408 ms 500064 KB Output is correct
3 Correct 479 ms 477304 KB Output is correct