CSES - APIO 2012

Submission details
Task:	Kunai
Sender:	ollpu
Submission time:	2019-03-16 19:01:01 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	30
#3	ACCEPTED	60

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3	details
#2	ACCEPTED	0.03 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.03 s	1, 2, 3	details
#6	ACCEPTED	0.02 s	1, 2, 3	details
#7	ACCEPTED	0.02 s	2, 3	details
#8	ACCEPTED	0.02 s	2, 3	details
#9	ACCEPTED	0.03 s	2, 3	details
#10	ACCEPTED	0.02 s	2, 3	details
#11	ACCEPTED	0.02 s	2, 3	details
#12	ACCEPTED	0.02 s	2, 3	details
#13	ACCEPTED	0.02 s	2, 3	details
#14	ACCEPTED	0.02 s	2, 3	details
#15	ACCEPTED	0.02 s	2, 3	details
#16	ACCEPTED	0.03 s	2, 3	details
#17	ACCEPTED	0.03 s	2, 3	details
#18	ACCEPTED	0.03 s	2, 3	details
#19	ACCEPTED	0.02 s	2, 3	details
#20	ACCEPTED	0.02 s	2, 3	details
#21	ACCEPTED	0.01 s	2, 3	details
#22	ACCEPTED	0.81 s	3	details
#23	ACCEPTED	0.54 s	3	details
#24	ACCEPTED	0.60 s	3	details
#25	ACCEPTED	0.77 s	3	details
#26	ACCEPTED	0.67 s	3	details
#27	ACCEPTED	0.83 s	3	details
#28	ACCEPTED	0.76 s	3	details
#29	ACCEPTED	0.55 s	3	details
#30	ACCEPTED	0.60 s	3	details
#31	ACCEPTED	0.77 s	3	details
#32	ACCEPTED	0.68 s	3	details
#33	ACCEPTED	0.82 s	3	details
#34	ACCEPTED	0.79 s	3	details
#35	ACCEPTED	0.54 s	3	details
#36	ACCEPTED	0.60 s	3	details
#37	ACCEPTED	0.78 s	3	details
#38	ACCEPTED	0.69 s	3	details
#39	ACCEPTED	0.81 s	3	details
#40	ACCEPTED	0.77 s	3	details
#41	ACCEPTED	0.55 s	3	details
#42	ACCEPTED	0.60 s	3	details
#43	ACCEPTED	0.76 s	3	details
#44	ACCEPTED	0.68 s	3	details
#45	ACCEPTED	0.81 s	3	details
#46	ACCEPTED	0.78 s	3	details
#47	ACCEPTED	0.53 s	3	details
#48	ACCEPTED	0.62 s	3	details
#49	ACCEPTED	0.77 s	3	details
#50	ACCEPTED	0.68 s	3	details
#51	ACCEPTED	0.83 s	3	details
#52	ACCEPTED	0.78 s	3	details
#53	ACCEPTED	0.54 s	3	details
#54	ACCEPTED	0.61 s	3	details
#55	ACCEPTED	0.78 s	3	details
#56	ACCEPTED	0.68 s	3	details
#57	ACCEPTED	0.84 s	3	details

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int z[101010];
int x[101010], y[101010], d[101010];
map<int, map<int, int>> rc[4], dg[4][2];
int gdg(int i, int w) {
  if (w) return x[i]+y[i];
  else return x[i]-y[i];
}
void add(int i) {
  if (d[i] % 2) {
    rc[d[i]][x[i]][y[i]] = i;
  } else {
    rc[d[i]][y[i]][x[i]] = i;
  }
  dg[d[i]][0][gdg(i, 0)][x[i]] = i;
  dg[d[i]][1][gdg(i, 1)][x[i]] = i;
}
void rem(int i, int t) {
  z[i] = t;
  if (d[i] % 2) {
    rc[d[i]][x[i]].erase(y[i]);
  } else {
    rc[d[i]][y[i]].erase(x[i]);
  }
  dg[d[i]][0][gdg(i, 0)].erase(x[i]);
  dg[d[i]][1][gdg(i, 1)].erase(x[i]);
}
pair<int, int> f(int i) {
  pair<int, int> res = {2.1e9, -1};
  map<int, int>::iterator it;
  if (d[i] == 0) {
    it = rc[2][y[i]].upper_bound(x[i]);
    if (it != rc[2][y[i]].end()) {
      pair<int, int> cres = *it;
      cres.F = cres.F - x[i];
      res = min(res, cres);
    }
    
    it = dg[3][1][gdg(i, 1)].upper_bound(x[i]);
    if (it != dg[3][1][gdg(i, 1)].end()) {
      pair<int, int> cres = *it;
      cres.F = (cres.F - x[i])*2;
      res = min(res, cres);
    }
  } else if (d[i] == 1) {
    it = dg[0][0][gdg(i, 0)].upper_bound(x[i]);
    if (it != dg[0][0][gdg(i, 0)].begin()) {
      it--;
      pair<int, int> cres = *it;
      cres.F = (x[i] - cres.F)*2;
      res = min(res, cres);
    }
  } else if (d[i] == 2) {
    it = dg[1][1][gdg(i, 1)].upper_bound(x[i]);
    if (it != dg[1][1][gdg(i, 1)].begin()) {
      it--;
      pair<int, int> cres = *it;
      cres.F = (x[i] - cres.F)*2;
      res = min(res, cres);
    }
  } else {
    it = rc[1][x[i]].upper_bound(y[i]);
    if (it != rc[1][x[i]].end()) {
      pair<int, int> cres = *it;
      cres.F = cres.F - y[i];
      res = min(res, cres);
    }
    
    it = dg[2][0][gdg(i, 0)].upper_bound(x[i]);
    if (it != dg[2][0][gdg(i, 0)].end()) {
      pair<int, int> cres = *it;
      cres.F = (cres.F - x[i])*2;
      res = min(res, cres);
    }
  }
  return res;
}

const int N = 1<<17;
int sp[2*N];
void sp_add(int p, int v) {
  p += N;
  do {
    sp[p] += v;
  } while (p /= 2);
}
int sp_sum(int a, int b) {
  a += N; b += N;
  int res = 0;
  while (a <= b) {
    if (a&1) res += sp[a++];
    if (~b&1) res += sp[b--];
    a /= 2; b /= 2;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int w, h, n;
  cin >> w >> h >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i] >> d[i];
    add(i);
  }
  using X = pair<int, pair<int, int>>;
  priority_queue<X> q;
  for (int i = 0; i < n; ++i) {
    auto p = f(i);
    if (p.S != -1) q.push({-p.F, {i, p.S}});
  }
  while (!q.empty()) {
    X x = q.top();
    q.pop();
    bool ivl = (z[x.S.F] && z[x.S.F] < -x.F) || (z[x.S.S] && z[x.S.S] < -x.F);
    if (ivl) {
      if (!z[x.S.F]) {
        auto p = f(x.S.F);
        if (p.S != -1) q.push({-p.F, {x.S.F, p.S}});
      }
      if (!z[x.S.S]) {
        auto p = f(x.S.S);
        if (p.S != -1) q.push({-p.F, {x.S.S, p.S}});
      }
    } else {
      rem(x.S.F, -x.F);
      rem(x.S.S, -x.F);
    }
  }
  // for (int i = 0; i < n; ++i) {
  //   cout << z[i] << " ";
  // }
  // cout << endl;
  map<int, vector<pair<int, int>>> sg[2], sf[2];
  for (int i = 0; i < n; ++i) {
    if (d[i] == 0) {
      int e = z[i] ? x[i]+z[i]/2 : w;
      sg[0][y[i]].emplace_back(x[i], e);
    } else if (d[i] == 1) {
      int e = z[i] ? y[i]-z[i]/2 : 1;
      sg[1][x[i]].emplace_back(e, y[i]);
    } else if (d[i] == 2) {
      int e = z[i] ? x[i]-z[i]/2 : 1;
      sg[0][y[i]].emplace_back(e, x[i]);
    } else {
      int e = z[i] ? y[i]+z[i]/2 : h;
      sg[1][x[i]].emplace_back(y[i], e);
    }
  }
  long res = 0;
  map<int, int> pk;
  struct E {
    int p, t, h;
    bool operator<(E o) const {
      if (p == o.p) return t < o.t;
      else return p < o.p;
    }
  };
  vector<E> ev;
  for (int g = 0; g < 2; ++g)
  for (auto &p : sg[g]) {
    sort(p.S.begin(), p.S.end());
    auto &trg = sf[g][p.F];
    for (auto q : p.S) {
      if (trg.size() && trg.back().S+1 >= q.F) {
        trg.back().S = max(trg.back().S, q.S);
      } else {
        trg.push_back(q);
      }
    }
    for (auto q : trg) {
      res += q.S-q.F+1;
    }
    if (g == 0) {
      pk[p.F] = 0;
      for (auto qx : trg) {
        ev.push_back({qx.F, 0, p.F});
        ev.push_back({qx.S, 2, p.F});
      }
    } else {
      ev.push_back({p.F, 1, -1});
    }
  }
  int c = 0;
  for (auto &p : pk) {
    p.S = c++;
  }
  pk[2e9] = c++;
  sort(ev.begin(), ev.end());
  for (E e : ev) {
    if (e.t == 0) {
      sp_add(pk[e.h], 1);
    } else if (e.t == 2) {
      sp_add(pk[e.h], -1);
    } else {
      for (pair<int, int> qx : sf[1][e.p]) {
        int a, b;
        a = pk.lower_bound(qx.F)->S;
        b = pk.upper_bound(qx.S)->S;
        b--;
        res -= sp_sum(a, b);
      }
    }
  }
  cout << res << endl;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 395 147 2 312 997 3 575 326 1 ...` view save

correct output
`351232` view save

user output
`351232` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 613 767 3 847 338 0 65 684 2 ...` view save

correct output
`341331` view save

user output
`341331` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 545 235 1 751 441 2 393 441 0 ...` view save

correct output
`2332` view save

user output
`2332` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 508 691 1 88 522 2 594 543 2 ...` view save

correct output
`91488` view save

user output
`91488` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`987 863 1000 337 215 1 426 724 0 314 667 2 ...` view save

correct output
`304733` view save

user output
`304733` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 134 885 1 99 920 2 853 166 1 ...` view save

correct output
`50224` view save

user output
`50224` view save

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 622691628 400169593 1 88321523 864579498 2 112795648 764418241 2 ...` view save

correct output
`510718011549` view save

user output
`510718011549` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 434001832 559301213 3 434001832 429662335 3 406314803 401975306 0 ...` view save

correct output
`2291715446` view save

user output
`2291715446` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 147530776 854510 0 356276711 182273622 1 892824604 150655760 0 ...` view save

correct output
`88532373705` view save

user output
`88532373705` view save

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`987285921 863112267 1000 470324395 497062190 3 442802251 378184556 2 119175366 201807368 0 ...` view save

correct output
`455873598338` view save

user output
`455873598338` view save

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 909404004 181534702 2 484518608 606420098 1 218950493 871988213 2 ...` view save

correct output
`27655301105` view save

user output
`27655301105` view save

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 773022132 211005023 2 999330973 728414009 3 788418382 315547103 0 ...` view save

correct output
`481150067104` view save

user output
`481150067104` view save

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 50373611 409198926 0 450050051 9522486 1 450050051 329920540 1 ...` view save

correct output
`2849288541` view save

user output
`2849288541` view save

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 541475743 439195694 1 704685352 411213621 0 541475743 919546919 3 ...` view save

correct output
`82091697388` view save

user output
`82091697388` view save

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
`987285921 863112267 1000 620654899 592269001 0 206328053 105131334 2 782084021 752936230 2 ...` view save

correct output
`467023572658` view save

user output
`467023572658` view save

Test 16

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 561552965 495764463 2 359727447 697589981 2 465263943 592053485 1 ...` view save

correct output
`25388296783` view save

user output
`25388296783` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 589070350 565712291 0 841681509 118453997 3 572166871 967138461 1 ...` view save

correct output
`508058157318` view save

user output
`508058157318` view save

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 466098270 174395571 1 708125245 416422546 2 596968012 416422546 2 ...` view save

correct output
`4246358023` view save

user output
`4246358023` view save

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 384004974 137019999 3 407193458 545911984 3 402045605 540764131 0 ...` view save

correct output
`79305870521` view save

user output
`79305870521` view save

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
`987285921 863112267 1000 449417196 662604888 1 48678588 632059056 2 565832510 404527588 0 ...` view save

correct output
`463406908716` view save

user output
`463406908716` view save

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
`1000000000 1000000000 1000 475820435 547875716 2 167693733 856002418 1 449458888 574237263 1 ...` view save

correct output
`41055207693` view save

user output
`41055207693` view save

Test 22

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 663138948 732069328 2 335193741 619561225 2 228849515 139776269 1 ...` view save

correct output
`49941362127608` view save

user output
`49941362127608` view save

Test 23

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 566759277 849622939 3 250197041 533060703 0 852403088 533060703 2 ...` view save

correct output
`39994458607` view save

user output
`39994458607` view save

Test 24

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 856953368 114383681 3 850373774 417536320 2 506532450 913767411 3 ...` view save

correct output
`8477051419311` view save

user output
`8477051419311` view save

Test 25

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 750078204 431759396 3 735927921 507211726 2 89989784 643673044 3 ...` view save

correct output
`46150537505050` view save

user output
`46150537505050` view save

Test 26

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 942 795 2 446 469 1 768 800 0 ...` view save

correct output
`1054717` view save

user output
`1054717` view save

Test 27

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 137117336 890747686 1 384041069 643823953 1 29726055 998138967 2 ...` view save

correct output
`476523338176` view save

user output
`476523338176` view save

Test 28

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 331703518 86776596 3 177544276 9601214 2 12598004 791367628 2 ...` view save

correct output
`50126205700926` view save

user output
`50126205700926` view save

Test 29

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 276411077 540284323 0 435323848 381371552 1 435323848 625003151 3 ...` view save

correct output
`56095255153` view save

user output
`56095255153` view save

Test 30

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 908028273 567997813 2 572250164 903775922 3 236472055 567997813 0 ...` view save

correct output
`8253896297688` view save

user output
`8253896297688` view save

Test 31

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 63453291 200913904 1 262979526 382364396 3 428521173 461559387 3 ...` view save

correct output
`46229727046871` view save

user output
`46229727046871` view save

Test 32

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 511 323 0 956 419 1 81 48 0 ...` view save

correct output
`1055185` view save

user output
`1055185` view save

Test 33

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 657870508 354607304 2 491838553 520639259 1 660690262 351787550 2 ...` view save

correct output
`507526568312` view save

user output
`507526568312` view save

Test 34

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 147751737 294000216 1 19894811 252157555 2 943830141 442958986 3 ...` view save

correct output
`49957015480521` view save

user output
`49957015480521` view save

Test 35

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 450108760 547507943 0 451372067 546244636 1 315061883 547507943 0 ...` view save

correct output
`62352343214` view save

user output
`62352343214` view save

Test 36

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 93427566 250549170 3 556201946 314045627 1 655446864 413290545 2 ...` view save

correct output
`8258222391750` view save

user output
`8258222391750` view save

Test 37

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 706589704 692508905 3 105330061 488033004 3 212269662 113150745 0 ...` view save

correct output
`46221255626007` view save

user output
`46221255626007` view save

Test 38

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 746 684 2 99 227 1 880 315 1 ...` view save

correct output
`1056052` view save

user output
`1056052` view save

Test 39

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 72121795 956404235 1 977020574 51505456 2 435320669 593205361 1 ...` view save

correct output
`407410639854` view save

user output
`407410639854` view save

Test 40

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 482034022 897612026 0 941070079 873435725 2 835704386 342496489 0 ...` view save

correct output
`49919072427797` view save

user output
`49919072427797` view save

Test 41

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 519936637 258601371 1 763550477 502215211 2 519936637 745829051 3 ...` view save

correct output
`44497041760` view save

user output
`44497041760` view save

Test 42

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 487637375 302473543 1 591230757 406066925 2 487637375 509660307 3 ...` view save

correct output
`8307354131507` view save

user output
`8307354131507` view save

Test 43

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 856920207 366456602 0 856141785 636238896 3 875178317 664279607 2 ...` view save

correct output
`46179682182549` view save

user output
`46179682182549` view save

Test 44

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 17 190 3 868 463 2 483 978 3 ...` view save

correct output
`1056218` view save

user output
`1056218` view save

Test 45

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 391529494 653705763 1 112895171 932340086 1 69191361 976043896 2 ...` view save

correct output
`568892059623` view save

user output
`568892059623` view save

Test 46

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 298082241 104835646 2 783420614 115992066 2 619452875 994087848 1 ...` view save

correct output
`49997496156308` view save

user output
`49997496156308` view save

Test 47

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 621949231 509438831 2 535984856 595403206 3 450020481 509438831 0 ...` view save

correct output
`51467675232` view save

user output
`51467675232` view save

Test 48

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 877374451 447747847 2 537306871 787815427 3 197239291 447747847 0 ...` view save

correct output
`8314959264748` view save

user output
`8314959264748` view save

Test 49

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 685682505 858051603 1 698492320 741907504 3 658926806 315870965 3 ...` view save

correct output
`46246375985396` view save

user output
`46246375985396` view save

Test 50

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 314 212 3 610 176 2 139 78 1 ...` view save

correct output
`1056041` view save

user output
`1056041` view save

Test 51

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 900809794 96891967 1 784333884 263748228 2 62490464 985591648 2 ...` view save

correct output
`442226775128` view save

user output
`442226775128` view save

Test 52

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 114130459 459542914 0 625771149 506032054 2 403201364 645679206 2 ...` view save

correct output
`50026483129307` view save

user output
`50026483129307` view save

Test 53

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 880347982 516662451 2 552033074 844977359 3 223718166 516662451 0 ...` view save

correct output
`48456523650` view save

user output
`48456523650` view save

Test 54

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 586976368 613454196 3 410434589 436912417 0 586976368 260370638 1 ...` view save

correct output
`8303589567989` view save

user output
`8303589567989` view save

Test 55

Group: 3

Verdict: ACCEPTED

input
`987285921 863112267 100000 170295294 135611110 1 383193391 511391566 3 226423785 40312796 2 ...` view save

correct output
`46287075850758` view save

user output
`46287075850758` view save

Test 56

Group: 3

Verdict: ACCEPTED

input
`1027 1039 100000 612 757 0 352 412 2 823 741 2 ...` view save

correct output
`1055250` view save

user output
`1055250` view save

Test 57

Group: 3

Verdict: ACCEPTED

input
`1000000000 1000000000 100000 652150584 446262032 1 811568386 286844230 1 492561855 605850761 1 ...` view save

correct output
`614169021291` view save

user output
`614169021291` view save

APIO 2012

Kunai

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Tasks

Submissions (ollpu)