oj.uz

답안 #595065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595065 2022-07-13T10:21:10 Z lohacho Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 48256 KB 
#include <bits/stdc++.h>
using namespace std;

const int NS = 120004, QS = (int)1e5 + 4;
int n, m, q, B;
pair<int, int> a[NS];
int col[NS];
vector<int> gr[NS];
int ind[NS][2];
pair<int, int> range[NS][2];
pair<int, int> p[2];
int ans[QS];

struct Data{
    int l, r, sum, lazy;
    Data(){}
};
int tN, st[NS];
Data tr[NS * 100];

void push(int x, int l, int r, int pl, int pr, int val){
    if(pl <= l && pr >= r){
        tr[x].sum += val;
        tr[x].lazy += val;
        return;
    }
    if(tr[x].lazy){
        ++tN; tr[tN] = tr[tr[x].l];
        tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy;
        ++tN; tr[tN] = tr[tr[x].r];
        tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy;
        tr[x].l = tN - 1, tr[x].r = tN;
        tr[x].lazy = 0;
    }
    int m = l + r >> 1;
    if(!(pr < l || pl > m)){
        ++tN, tr[tN] = tr[tr[x].l], tr[x].l = tN;
        push(tr[x].l, l, m, pl, pr, val);
    }
    if(!(pr <= m || pl > r)){
        ++tN, tr[tN] = tr[tr[x].r], tr[x].r = tN;
        push(tr[x].r, m + 1, r, pl, pr, val);
    }
    tr[x].sum = tr[tr[x].l].sum + tr[tr[x].r].sum;
}

int get(int pre, int x, int l, int r, int fl, int fr){
    if(fl <= l && fr >= r) return tr[x].sum - tr[pre].sum;
    if(tr[x].lazy){
        ++tN; tr[tN] = tr[tr[x].l];
        tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy;
        ++tN; tr[tN] = tr[tr[x].r];
        tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy;
        tr[x].l = tN - 1, tr[x].r = tN;
        tr[x].lazy = 0;
    }
    if(tr[pre].lazy){
        ++tN; tr[tN] = tr[tr[pre].l];
        tr[tN].sum += tr[pre].lazy, tr[tN].lazy += tr[pre].lazy;
        ++tN; tr[tN] = tr[tr[pre].r];
        tr[tN].sum += tr[pre].lazy, tr[tN].lazy += tr[pre].lazy;
        tr[pre].l = tN - 1, tr[pre].r = tN;
        tr[pre].lazy = 0;
    }
    int m = l + r >> 1;
    int rv = 0;
    if(!(fr < l || fl > m)){
        rv += get(tr[pre].l, tr[x].l, l, m, fl, fr);
    }
    if(!(fr <= m || fl > r)){
        rv += get(tr[pre].r, tr[x].r, m + 1, r, fl, fr);
    }
    return rv;
}

int ccw(pair<int, int> bs, pair<int, int> x, pair<int, int> y){
    x.first -= bs.first, x.second -= bs.second;
    y.first -= bs.first, y.second -= bs.second;
    long long val = (long long)x.first * y.second - (long long)x.second * y.first;
    return (val ? val > 0 ? 1 : -1 : 0);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second >> col[i];
        --col[i];
        gr[col[i]].push_back(i);
    }
    cin >> p[0].first >> p[0].second >> p[1].first >> p[1].second;
    for(int k = 0; k < 2; ++k){
        vector<vector<int>> u, d;
        for(int j = 0; j < n; ++j){
            if(a[j].second > p[k].second || (a[j].second == p[k].second && a[j].first < p[k].first)){
                u.push_back({a[j].first, a[j].second, j});
            }
            else{
                d.push_back({a[j].first, a[j].second, j});
            }
        }
        auto comp = [&](vector<int>&x, vector<int>&y){return ccw(p[k], {x[0], x[1]}, {y[0], y[1]}) < 0;};
        sort(u.begin(), u.end(), comp), sort(d.begin(), d.end(), comp);
        for(auto&i:d){
            u.push_back(i);
        }
        int r = 0, ldir = 0;
        for(int l = 0; l < (int)u.size(); ++l){
            int dir = ((k == 0) ^ (ccw({u[l][0], u[l][1]}, p[0], p[1]) == -1));
            dir = (dir ? 1 : -1);
            if(ldir && dir != ldir){
                r = l;
            }
            ldir = dir;
            while(true){
                int ca = ccw(p[k], {u[l][0], u[l][1]}, {u[r][0], u[r][1]});
                int cb = ccw(p[k], {u[l][0], u[l][1]}, p[1 - k]);
                if(ca == cb || !ca || !cb) break;
                r = (r - dir + (int)u.size()) % (int)u.size();
            }
            while(true){
                int nr = (r + dir + (int)u.size()) % (int)u.size();
                int ca = ccw(p[k], {u[l][0], u[l][1]}, {u[nr][0], u[nr][1]});
                int cb = ccw(p[k], {u[l][0], u[l][1]}, p[1 - k]);
                if(ca != cb) break;
                r = nr;
            }
            ind[u[l][2]][k] = l;
            if(ccw(p[k], {u[l][0], u[l][1]}, {u[r][0], u[r][1]}) == -1){
                range[u[l][2]][k] = {l, r + (r < l ? n : 0)};
            }
            else{
                range[u[l][2]][k] = {r, l + (l < r ? n : 0)};
            }
        }
    }
    B = 200;
    vector<vector<int>> q1, q2, q3;
    cin >> q;
    for(int i = 0; i < q; ++i){
        int x, y; cin >> x >> y; --x, --y;
        if((int)gr[x].size() < B && (int)gr[y].size() < B){
            q1.push_back({x, y, i});
        }
        else if((int)gr[x].size() < B){
            q2.push_back({x, y, i});
        }
        else{
            q3.push_back({x, y, i});
        }
    }
    for(auto&rep:q1){
        int x = rep[0], y = rep[1], id = rep[2];
        int dap = 0;
        for(int i = 0; i < (int)gr[x].size(); ++i){
            for(int j = 0; j < (int)gr[y].size(); ++j){
                if(ind[gr[y][j]][0] >= range[gr[x][i]][0].first && ind[gr[y][j]][0] <= range[gr[x][i]][0].second){
                    if(ind[gr[y][j]][1] >= range[gr[x][i]][1].first && ind[gr[y][j]][1] <= range[gr[x][i]][1].second) ++dap;
                }
                if(ind[gr[y][j]][0] + n >= range[gr[x][i]][0].first && ind[gr[y][j]][0] + n <= range[gr[x][i]][0].second){
                    if(ind[gr[y][j]][1] >= range[gr[x][i]][1].first && ind[gr[y][j]][1] <= range[gr[x][i]][1].second) ++dap;
                }
                if(ind[gr[y][j]][0] >= range[gr[x][i]][0].first && ind[gr[y][j]][0] <= range[gr[x][i]][0].second){
                    if(ind[gr[y][j]][1] + n >= range[gr[x][i]][1].first && ind[gr[y][j]][1] + n <= range[gr[x][i]][1].second) ++dap;
                }
                if(ind[gr[y][j]][0] + n >= range[gr[x][i]][0].first && ind[gr[y][j]][0] + n <= range[gr[x][i]][0].second){
                    if(ind[gr[y][j]][1] + n >= range[gr[x][i]][1].first && ind[gr[y][j]][1] + n <= range[gr[x][i]][1].second) ++dap;
                }
            }
        }
        vector<pair<int, int>> srt;
        for(int j = 0; j < (int)gr[y].size(); ++j){
            srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1]});
            srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1] + n});
            srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1]});
            srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1] + n});
        }
        sort(srt.begin(), srt.end());
        tN = 0;
        for(int i = 0; i < (int)srt.size(); ++i){
            st[i] = ++tN; tr[tN] = tr[i ? st[i - 1] : 0];
            push(st[i], 0, 2 * n - 1, srt[i].second, srt[i].second, 1);
        }
        int nans = 0;
        for(int i = 0; i < (int)gr[x].size(); ++i){
            int p2 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][i]][0].second + 1, -(int)1e9)) - srt.begin() - 1;
            int p1 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][i]][0].first, -(int)1e9)) - srt.begin();
            nans += get(p1 > 0 ? st[p1 - 1] : 0, st[p2], 0, 2 * n - 1, range[gr[x][i]][1].first, range[gr[x][i]][1].second);
        }
        ans[id] = nans;
    }
    sort(q2.begin(), q2.end(), [&](vector<int>&x, vector<int>&y){return x[1] < y[1];});
    vector<pair<int, int>> srt;
    for(int i = 0; i < (int)q2.size(); ++i){
        int x = q2[i][0], y = q2[i][1], id = q2[i][2];
        if(!i || y != q2[i - 1][1]){
            srt.clear();
            for(int j = 0; j < (int)gr[y].size(); ++j){
                srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1]});
                srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1] + n});
                srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1]});
                srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1] + n});
            }
            sort(srt.begin(), srt.end());
            tN = 0;
            for(int k = 0; k < (int)srt.size(); ++k){
                st[k] = ++tN; tr[tN] = tr[k ? st[k - 1] : 0];
                push(st[k], 0, 2 * n - 1, srt[k].second, srt[k].second, 1);
            }
        }
        int nans = 0;
        for(int j = 0; j < (int)gr[x].size(); ++j){
            int p2 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][j]][0].second + 1, -(int)1e9)) - srt.begin() - 1;
            int p1 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][j]][0].first, -(int)1e9)) - srt.begin();
            nans += get(p1 > 0 ? st[p1 - 1] : 0, st[p2], 0, 2 * n - 1, range[gr[x][j]][1].first, range[gr[x][j]][1].second);
        }
        ans[id] = nans;
    }
    sort(q3.begin(), q3.end(), [&](vector<int>&x, vector<int>&y){return x[0] < y[0];});
    vector<vector<int>> srt2;
    for(int i = 0; i < (int)q3.size(); ++i){
        int x = q3[i][0], y = q3[i][1], id = q3[i][2];
        if(!i || x != q3[i - 1][0]){
            srt2.clear();
            for(int j = 0; j < (int)gr[x].size(); ++j){
                srt2.push_back({range[gr[x][j]][0].first, range[gr[x][j]][1].first, range[gr[x][j]][1].second, 1});
                srt2.push_back({range[gr[x][j]][0].second + 1, range[gr[x][j]][1].first, range[gr[x][j]][1].second, -1});
            }
            sort(srt2.begin(), srt2.end());
            tN = 0;
            for(int k = 0; k < (int)srt2.size(); ++k){
                st[k] = ++tN; tr[tN] = tr[k ? st[k - 1] : 0];
                push(st[k], 0, 2 * n - 1, srt2[k][1], srt2[k][2], srt2[k][3]);
            }
        }
        int nans = 0;
        for(int j = 0; j < (int)gr[y].size(); ++j){
            int fx = ind[gr[y][j]][0], fy = ind[gr[y][j]][1];
            int p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1;
            nans += get(0, st[p2], 0, 2 * n - 1, fy, fy);

            fy += n;
            p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1;
            nans += get(0, st[p2], 0, 2 * n - 1, fy, fy);

            fx += n;
            p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1;
            nans += get(0, st[p2], 0, 2 * n - 1, fy, fy);

            fy -= n;
            p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1;
            nans += get(0, st[p2], 0, 2 * n - 1, fy, fy);
        }
        ans[id] = nans;
    }
    for(int i = 0; i < q; ++i){
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

dragon2.cpp: In function 'void push(int, int, int, int, int, int)':
dragon2.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m = l + r >> 1;
      |             ~~^~~
dragon2.cpp: In function 'int get(int, int, int, int, int, int)':
dragon2.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 17 ms 4496 KB Output is correct
3 Correct 148 ms 3712 KB Output is correct
4 Correct 307 ms 9308 KB Output is correct
5 Correct 118 ms 9412 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 7 ms 5452 KB Output is correct
9 Correct 6 ms 4444 KB Output is correct
10 Correct 5 ms 4444 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 42608 KB Output is correct
2 Correct 238 ms 18304 KB Output is correct
3 Correct 78 ms 7108 KB Output is correct
4 Correct 30 ms 7032 KB Output is correct
5 Correct 30 ms 7820 KB Output is correct
6 Correct 62 ms 18384 KB Output is correct
7 Correct 69 ms 19000 KB Output is correct
8 Correct 61 ms 28408 KB Output is correct
9 Correct 44 ms 18636 KB Output is correct
10 Correct 43 ms 18364 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 17 ms 4496 KB Output is correct
3 Correct 148 ms 3712 KB Output is correct
4 Correct 307 ms 9308 KB Output is correct
5 Correct 118 ms 9412 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 7 ms 5452 KB Output is correct
9 Correct 6 ms 4444 KB Output is correct
10 Correct 5 ms 4444 KB Output is correct
11 Correct 107 ms 42608 KB Output is correct
12 Correct 238 ms 18304 KB Output is correct
13 Correct 78 ms 7108 KB Output is correct
14 Correct 30 ms 7032 KB Output is correct
15 Correct 30 ms 7820 KB Output is correct
16 Correct 62 ms 18384 KB Output is correct
17 Correct 69 ms 19000 KB Output is correct
18 Correct 61 ms 28408 KB Output is correct
19 Correct 44 ms 18636 KB Output is correct
20 Correct 43 ms 18364 KB Output is correct
21 Correct 90 ms 42472 KB Output is correct
22 Correct 288 ms 18252 KB Output is correct
23 Correct 1353 ms 13068 KB Output is correct
24 Correct 3620 ms 10628 KB Output is correct
25 Correct 376 ms 10596 KB Output is correct
26 Correct 184 ms 10844 KB Output is correct
27 Correct 41 ms 7240 KB Output is correct
28 Correct 41 ms 7244 KB Output is correct
29 Correct 183 ms 48256 KB Output is correct
30 Correct 203 ms 40000 KB Output is correct
31 Correct 171 ms 47560 KB Output is correct
32 Correct 2041 ms 10888 KB Output is correct
33 Execution timed out 4043 ms 10768 KB Time limit exceeded
34 Halted 0 ms 0 KB -