Submission #1228614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228614		kfhjad	Plahte (COCI17_plahte)	C++20	96 / 160	134 ms	24988 KiB

plahte

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// sweep line up to each shot coordinate
// 

const int MX = 1E5;

vector<int> adj[MX];
set<int> cols[MX];
int totalColours[MX];
bool visited[MX];

void dfs(int node)
{
    if (visited[node])
        return;
        
    visited[node] = true;
    for (auto u : adj[node])
    {
        dfs(u);
        
        if (cols[node].size() < cols[u].size())
            swap(cols[node], cols[u]);
            
        cols[node].insert(cols[u].begin(), cols[u].end());
    }
    
    totalColours[node] = cols[node].size();
}

void add(auto& s, auto& event)
{
    auto it = s.upper_bound({event[1], 0});
    --it;
    int who = it -> second;
    
    s.insert({event[1], event[3]});
    s.insert({event[2] + 1, who});

    adj[who].push_back(event[3]);
}

void erase(auto& s, auto& event)
{
    auto it = s.find({event[1], event[3]});
    assert(it != s.end());

    it = s.erase(it);
    s.erase(it);
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    
    // x, y1, y2, index
    vector<array<int, 4>> events;
    
    for (int i = 1; i <= N; ++i)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        events.push_back({x1, y1, y2, i});
        events.push_back({x2 + 1, y1, y2, i + N});
    }
    
    sort(events.begin(), events.end(), [&](auto& a, auto& b)
    {
        if (a[0] == b[0])
        {
            if ((a[3] >= N) ^ (b[3] >= N))
                return a[3] >= N;
            else
                return a[1] < b[1];
        }
            
        return a[0] < b[0];
    });
    
    for (auto& i : events)
        if (i[3] > N) i[3] -= N;
            
    vector<array<int, 3>> shots(M);
    for (auto& [x, y, c] : shots)
        cin >> x >> y >> c;

    sort(shots.begin(), shots.end());
    
    // y1, index
    set<pair<int, int>> s;
    s.insert({0, 0});
    s.insert({(int)2E9, 0});
    
    int l = 0;
    for (auto& [x, y, c] : shots)
    {
        for (; l < 2 * N && events[l][0] <= x; ++l)
        {
            if (s.find({events[l][1], events[l][3]}) != s.end())
                erase(s, events[l]);
            else
                add(s, events[l]);
                
            // for (auto& i : s)
                // cout << i.first << ' ' << i.second << endl;
                // cout << endl;
        }
        
        auto it = s.upper_bound({y, (int)2E9});
        --it;
        
        cols[it -> second].insert(c);
    }
    
    for (int i = 1; i <= N; ++i)
        dfs(i);
    
    for (int i = 1; i <= N; ++i)
        cout << totalColours[i] << '\n';

    return 0;
}                              /*****************************=
                            -+**********************************= 
                        :-*****************************************+:
                    ..:*************+=+*******************************=.
                 ..-==*****************+=-+*****************************+.
               ..-=***********************+--+****************************= 
               :+**************#*#**********+--+***************************-  .=--=.  
             .+*********************#*********+--****************************++++----:        
            -+***********************##*********--+********************************+--=.      
           =****=**********************#*********+-=***************************#*****+--=     
         .=****+***********************************-=*********************#*****##*****=-=.   
        :=*****=************************************=-*****************#******#####*****=-=.  
       .=**+***=**************************#**********==***********##*******#**######*****+-=. 
       +***=***+***************************#**********-+*****####********#*****#####******+-=:
      =+**=****+****************#**********************-*####*********##***#*#######*******+-=.
     .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. 
     =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= 
    .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
    -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
    =*###+######+############################################=..+=-+.########%##%##%##########*-+* 
    +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
   .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
  .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
  .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
  .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%=  #%%############=###-
  .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+   #%%###########*=###+
  :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
   .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+     %%######%#####=*####.
    #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%-      %%######%#####=#####.
    -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%#        #%######%####*=###%#
     *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%*         #%######%####+*###%#
         *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%#          +%######%####=####%#.
          =.=###%%%%%:.............:............#*%%####*#*=====%@%%%           :%#####%%####+######:
           .=%##%%%%%*.............:............#*%%####+#+======%#%*        .:-=%%%%%%%%###+#####+#-
            .%%##%%%-*-..............::::.......#+%%####+#=====-...#:  :*%%%%%%%%%%%%%%%%###*#####=#=
            .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
             *-#%#%%-  -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
             =*.%%%%=   .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
              #..%%%#.    -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
              +- :%%%#+     =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
              .#. =%% .*=     -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
               .*  *%-         .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
                .=. ##         ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
                  ..=*-    .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
                           #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
                           *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
                           :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
                           .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
                           .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
                           ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
                             .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
                             .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
                             .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
                             -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
                             %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
                             *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
                             :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
                              :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
                               :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
                                 :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
                                -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
                                -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
                               -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
                              -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32