답안 #53859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53859 2018-07-01T12:12:36 Z grumpy_gordon Dragon 2 (JOI17_dragon2) C++17
60 / 100
4000 ms 28632 KB
/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef unsigned int uint;

ll sqr(ll x){
    return x * x;
}

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1227);

mt19937_64 rndll(12365);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 7;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

void setmin(ll &x, ll y){
    x = min(x, y);
}

void setmax(ll &x, ll y){
    x = max(x, y);
}

int gcd(int a, int b){
    return a ? gcd(b % a, a) : b;
}

const ll llinf = 2e18 + 100;

const double eps = 1e-9;

const int maxn = 3e4 + 10, maxw = 1e5 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 16;

struct fenwick{

    vector<int> q;

    void resz(int n){
        q.resize(n, 0);
    }

    void inc(int i, int v){
        for (; i < q.size(); i = (i | (i + 1)))
            q[i] += v;
    }

    int get(int i){
        int r = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1)
            r += q[i];
        return r;
    }
};

pair<int, int> dif(pair<int, int> x, pair<int, int> y){
    return make_pair(y.first - x.first, y.second - x.second);
}

ll cp(pair<int, int> x, pair<int, int> y){
    return x.first * (ll)y.second - x.second * (ll)y.first;
}

ll cp(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    return cp(dif(a, b), dif(a, c));
}

int quar(pair<int, int> x){
    return x.second >= 0;
}

int n, groups;

int zap;

int group[maxn];

pair<int, int> pt[maxn];

pair<int, int> segment[2];

int srt[2][2 * maxn];

int pos[maxn];

bool ups[maxn];

vector<pair<pair<int, int>, int> > que[maxn];

int pos1[maxn];

int answer[maxw];

fenwick q[maxn][2];

vector<int> arr[maxn][2];

int siz[maxn][2];

int get(int i, int j, int l, int r, int t){
    if (l > r)
        return 0;
    int w = q[i][j].get(r) - q[i][j].get(l - 1);
    if (t == 0)
        w = r - l + 1 - w;
    return w;
}

void add(int i, int v){
    q[group[i]][ups[i]].inc(pos[i], v);
    q[group[i]][ups[i]].inc(pos[i] + siz[group[i]][ups[i]], v);
}

void solve(){
    int last = 0;
    for (int iter = 0; iter < n; iter++){
        if (iter > 0)
            add(srt[0][iter - 1], -1);
        int i = srt[0][iter];
        while (last - iter < n && cp(segment[0], pt[i], pt[srt[0][last]]) >= 0)
            add(srt[0][last++], 1);
        for (auto its : que[group[i]]){
            int gr = its.first.first, tp = its.first.second, ansi = its.second;
            for (int t = 0; t < 2; t++){
                if (arr[gr][t].empty())
                    continue;
                int l, r;
                l = -1, r = siz[gr][t];
                while (r - l > 1){
                    int m = (l + r) / 2;
                    if (pos1[arr[gr][t][m]] > pos1[i])
                        r = m;
                    else
                        l = m;
                }
                int le, re;
                if (r == siz[gr][t])
                    r = 0;
                le = r;
                if (cp(segment[1], pt[i], pt[arr[gr][t][r]]) < 0)
                    re = le - 1;
                else{
                    l = r, r = l + siz[gr][t];
                    while (r - l > 1){
                        int m = (l + r) / 2;
                        if (cp(segment[1], pt[i], pt[arr[gr][t][m]]) > 0)
                            l = m;
                        else
                            r = m;
                    }
                    re = l;
                }
                if (cp(segment[0], pt[i], segment[1]) > 0)
                    answer[ansi] += get(gr, t, 0, siz[gr][t] - 1, 1) - get(gr, t, le, re, 1);
                else
                    answer[ansi] += get(gr, t, le, re, 0);
            }
        }
    }
}

void precalc(){
    cin >> n >> groups;
    for (int i = 0; i < n; i++){
        cin >> pt[i].first >> pt[i].second;
        cin >> group[i];
        group[i]--;
    }
    for (int i = 0; i < 2; i++)
        cin >> segment[i].first >> segment[i].second;
    if (segment[0] > segment[1])
        swap(segment[0], segment[1]);
    for (int t = 0; t < 2; t++){
        iota(srt[t], srt[t] + n, 0);
        sort(srt[t], srt[t] + n, [&](int i, int j){
                auto x = dif(segment[t], pt[i]), y = dif(segment[t], pt[j]);
                int w = quar(x), h = quar(y);
                if (w != h)
                    return w > h;
                return cp(x, y) > 0;
             });
        for (int i = 0; i < n; i++)
            srt[t][i + n] = srt[t][i];
    }
    for (int i = 0; i < n; i++)
        ups[i] = (cp(segment[0], segment[1], pt[i]) > 0);
    for (int it = 0; it < n; it++){
        int i = srt[1][it];
        pos[i] = siz[group[i]][ups[i]]++;
        arr[group[i]][ups[i]].push_back(i);
        pos1[i] = it;
    }
    for (int i = 0; i < groups; i++)
        for (int j = 0; j < 2; j++){
            q[i][j].resz(2 * siz[i][j]);
            for (int k = 0; k < siz[i][j]; k++)
                arr[i][j].push_back(arr[i][j][k]);
        }
    cin >> zap;
    for (int i = 0; i < zap; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (0 && arr[x][0].size() + arr[x][1].size() > arr[y][0].size() + arr[y][1].size())
            que[y].push_back(make_pair(make_pair(x, 1), i));
        else
            que[x].push_back(make_pair(make_pair(y, 0), i));
    }
}

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("gymnasts.in");
    //ofstream cout("gymnasts.out");
    //freopen("sort.in", "r", stdin);
    //freopen("sort.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    precalc();
    solve();
    for (int i = 0; i < zap; i++)
        cout << answer[i] << '\n';
}

Compilation message

dragon2.cpp: In member function 'void fenwick::inc(int, int)':
dragon2.cpp:186:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; i < q.size(); i = (i | (i + 1)))
                ~~^~~~~~~~~~
dragon2.cpp: In function 'void solve()':
dragon2.cpp:265:39: warning: unused variable 'tp' [-Wunused-variable]
             int gr = its.first.first, tp = its.first.second, ansi = its.second;
                                       ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4088 KB Output is correct
2 Correct 14 ms 4264 KB Output is correct
3 Correct 47 ms 4528 KB Output is correct
4 Correct 63 ms 7640 KB Output is correct
5 Correct 56 ms 9092 KB Output is correct
6 Correct 8 ms 9092 KB Output is correct
7 Correct 9 ms 9092 KB Output is correct
8 Correct 8 ms 9092 KB Output is correct
9 Correct 7 ms 9092 KB Output is correct
10 Correct 7 ms 9092 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9092 KB Output is correct
2 Correct 208 ms 9548 KB Output is correct
3 Correct 62 ms 10352 KB Output is correct
4 Correct 58 ms 11180 KB Output is correct
5 Correct 51 ms 12936 KB Output is correct
6 Correct 44 ms 12936 KB Output is correct
7 Correct 40 ms 13392 KB Output is correct
8 Correct 39 ms 13948 KB Output is correct
9 Correct 32 ms 14432 KB Output is correct
10 Correct 33 ms 14892 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4088 KB Output is correct
2 Correct 14 ms 4264 KB Output is correct
3 Correct 47 ms 4528 KB Output is correct
4 Correct 63 ms 7640 KB Output is correct
5 Correct 56 ms 9092 KB Output is correct
6 Correct 8 ms 9092 KB Output is correct
7 Correct 9 ms 9092 KB Output is correct
8 Correct 8 ms 9092 KB Output is correct
9 Correct 7 ms 9092 KB Output is correct
10 Correct 7 ms 9092 KB Output is correct
11 Correct 49 ms 9092 KB Output is correct
12 Correct 208 ms 9548 KB Output is correct
13 Correct 62 ms 10352 KB Output is correct
14 Correct 58 ms 11180 KB Output is correct
15 Correct 51 ms 12936 KB Output is correct
16 Correct 44 ms 12936 KB Output is correct
17 Correct 40 ms 13392 KB Output is correct
18 Correct 39 ms 13948 KB Output is correct
19 Correct 32 ms 14432 KB Output is correct
20 Correct 33 ms 14892 KB Output is correct
21 Correct 48 ms 15640 KB Output is correct
22 Correct 165 ms 16312 KB Output is correct
23 Correct 1529 ms 17148 KB Output is correct
24 Correct 1591 ms 21060 KB Output is correct
25 Correct 142 ms 23456 KB Output is correct
26 Correct 104 ms 25932 KB Output is correct
27 Correct 60 ms 25932 KB Output is correct
28 Correct 95 ms 26084 KB Output is correct
29 Execution timed out 4053 ms 28632 KB Time limit exceeded
30 Halted 0 ms 0 KB -