oj.uz

답안 #735829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735829 2023-05-04T18:22:04 Z TahirAliyev Plahte (COCI17_plahte) C++17
160 / 160
 547 ms 39652 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<int, int>


struct rect{
    int x1, y1, x2, y2;
};


const int MAX = 8e4 + 8;
int n, m;

rect rects[MAX];
pii paintballs[MAX];
int c[MAX];

int tree[int(1e6)];

void update(int pos, int val){
    for (int i = pos; i < 1e6; i += (-i) & i){
        tree[i] += val;
    }
}

int ask(int l, int r){
    if(l != 1) ask(1, r) - ask(1, l - 1);
    int res = 0;
    for (int i = r; i > 0; i -= (-i) & i){
        res += tree[i];
    }
    return res;
}

void input(){
    cin >> n >> m;
    map<int, int> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
        mp[rects[i].y1];
        mp[rects[i].y2];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> paintballs[i].first >> paintballs[i].second >> c[i];
        mp[paintballs[i].second];
    }
    int c = 1;
    for(auto& p:mp){
        p.second = c++;
    }
    for (int i = 1; i <= n; i++)
    {
        rects[i].y1 = mp[rects[i].y1];
        rects[i].y2 = mp[rects[i].y2];
    }
    for (int i = 1; i <= m; i++)
    {
        paintballs[i].second = mp[paintballs[i].second];
    }
    
}

vector<array<int, 3>> events;
int par[MAX << 1];
vector<int> g[MAX << 1];
set<int> sub[MAX << 1];
int ans[MAX << 1];

void dfs(int node){
    for(int to:g[node]){
        dfs(to);
        if(sub[node].size() < sub[to].size()){
            swap(sub[node], sub[to]);
        }
    }
    for(int to:g[node]){
        for(int a:sub[to]){
            sub[node].insert(a);
        }
    }
    if(node > n){
        sub[node].insert(c[node - n]);
    }
    ans[node] = sub[node].size();
}

int main(){
    input();
    for (int i = 1; i <= m; i++)
    {
        events.push_back({paintballs[i].first, 1, i});
    }
    for (int i = 1; i <= n; i++)
    {
        events.push_back({rects[i].x1, 0, i});
        events.push_back({rects[i].x2, 2, i});
    }
    sort(events.begin(), events.end());

    for(auto e : events){
        if(e[1] == 1){
            par[e[2] + n] = ask(1, paintballs[e[2]].second);
            g[par[e[2] + n]].push_back(e[2] + n);
            
        }
        else if(e[1] == 0){
            par[e[2]] = ask(1, rects[e[2]].y1);
            g[par[e[2]]].push_back(e[2]);

            update(rects[e[2]].y1, e[2] - par[e[2]]);
            update(rects[e[2]].y2 + 1, -(e[2] - par[e[2]]));
        }
        else{
            update(rects[e[2]].y1, -(e[2] - par[e[2]]));
            update(rects[e[2]].y2 + 1, e[2] - par[e[2]]);
        }
    }
    dfs(0);
    for(int i = 1; i <= n; ++i){
        cout << ans[i] << '\n';
    }
}

Compilation message

plahte.cpp: In function 'int ask(int, int)':
plahte.cpp:33:26: warning: value computed is not used [-Wunused-value]
   33 |     if(l != 1) ask(1, r) - ask(1, l - 1);
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 19864 KB Output is correct
2 Correct 143 ms 20300 KB Output is correct
3 Correct 7 ms 11600 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 21708 KB Output is correct
2 Correct 184 ms 20932 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 29216 KB Output is correct
2 Correct 318 ms 25832 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 545 ms 39652 KB Output is correct
2 Correct 547 ms 35320 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 496 ms 37784 KB Output is correct
2 Correct 461 ms 34536 KB Output is correct
3 Correct 9 ms 11664 KB Output is correct