oj.uz

Submission #715004

# Submission time Handle Problem Language Result Execution time Memory
715004 2023-03-25T17:27:56 Z TheSahib Plahte (COCI17_plahte) C++14
160 / 160
 537 ms 68392 KB 
#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 8e4 + 8;

struct BIT{
    vector<ll> tree;
    int n = 0;
    BIT(int _n){
        n = _n;
        tree.resize(n + 1, 0);
    }
    void update(int l, int r, int v){
        while(l <= n){
            tree[l] += v;
            l += l & -l;
        }
        r++;
        while(r <= n){
            tree[r] -= v;
            r += r & -r;
        }
    }
    ll ask(int pos){
        ll ans = 0;
        while(pos > 0){
            ans += tree[pos];
            pos -= pos & -pos;
        }
        return ans;
    }
};

struct event{
    int t, x, y1, y2, index;
};

bool comp(event& e1, event& e2){
    if(e1.x == e2.x){
        return e1.t < e2.t;
    }
    return e1.x < e2.x;
}

int n, m;
int squares[MAX][4];
int points[MAX][3];

vector<int> g[MAX * 3];
set<int> sets[MAX * 3];
int ans[MAX * 3];
int par[MAX * 3];

void dfs(int node){
    for(int to:g[node]){
        if(to == par[node]) continue;
        dfs(to);
        if(sets[node].size() < sets[to].size()){
            swap(sets[node], sets[to]);
        }
    }
    if(node > n){
        sets[node].insert(points[node - n - 1][2]);
    }
    for(int to:g[node]){
        if(to == par[node]) continue;
        for(int a:sets[to]){
            sets[node].insert(a);
        }
    }
    ans[node] = sets[node].size();
}

int main(){
    cin >> n >> m;
    map<int, int> mp;
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        cin >> squares[i][0] >> squares[i][1] >> squares[i][2] >> squares[i][3];
        v.push_back(squares[i][1]);
        v.push_back(squares[i][3]);
    }
    
    for (int i = 0; i < m; i++)
    {
        cin >> points[i][0] >> points[i][1] >> points[i][2];
        v.push_back(points[i][1]);
    }
    sort(v.begin(), v.end());
    int a = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if(i == 0 || v[i - 1] != v[i]) a++;
        mp[v[i]] = a;
    }
    vector<event> events;
    for (int i = 0; i < n; i++)
    {
        events.push_back({0, squares[i][0], mp[squares[i][1]], mp[squares[i][3]], i + 1});
        events.push_back({2, squares[i][2], mp[squares[i][1]], mp[squares[i][3]], i + 1});
    }
    for (int i = 0; i < m; i++)
    {
        events.push_back({1, points[i][0], mp[points[i][1]], mp[points[i][1]], i + n + 1});
    }
    BIT fenw(1e6);
    sort(events.begin(), events.end(), comp);
    for(event e:events){
        if(e.t <= 1){
            par[e.index] = fenw.ask(e.y1);
            g[e.index].push_back(par[e.index]);
            g[par[e.index]].push_back(e.index);
            
            if(e.t == 0){
                fenw.update(e.y1, e.y2, -par[e.index] + e.index);
            }
        }
        else{
            fenw.update(e.y1, e.y2, -e.index + par[e.index]);
        }
    }
    
    dfs(0);
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 38416 KB Output is correct
2 Correct 185 ms 38948 KB Output is correct
3 Correct 20 ms 25032 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 40576 KB Output is correct
2 Correct 215 ms 39800 KB Output is correct
3 Correct 17 ms 25028 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 52276 KB Output is correct
2 Correct 327 ms 48416 KB Output is correct
3 Correct 13 ms 24984 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 68392 KB Output is correct
2 Correct 505 ms 64128 KB Output is correct
3 Correct 14 ms 25052 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 66676 KB Output is correct
2 Correct 537 ms 62760 KB Output is correct
3 Correct 13 ms 25096 KB Output is correct