oj.uz

Submission #973556

# Submission time Handle Problem Language Result Execution time Memory
973556 2024-05-02T07:13:15 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1318 ms 154132 KB 
#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+20;

struct BIT2d{
   int n;
   vector<pair<int, int>> t[N];
   void init(int _n){
      n=_n;
      for (int i=1; i<=n; ++i) t[i].emplace_back(-1, 0);
   }
   void fake_update(int x, int y){
      for (int i=x; i<=n; i+=i&(-i)) t[i].emplace_back(y, 0);
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int x, int y, int val){
      for (int i=x; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second+=val;
         }
      }
   }
   int get(int x, int y){
      int ans=0;
      for (int i=x; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j; j-=j&(-j)){
            ans+=t[i][j].second;
         }
      }
      return ans;
   }
   int get(int x, int y, int z, int t){
      if (x>z || y>t) return 0;
      return get(z, t)-get(z, y-1)-get(x-1, t)+get(x-1, y-1);
   }
} bit1, bit2, bit3, bit4;

const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
   r=R, c=C;
   bit1.init(r);
   bit2.init(r+1);
   bit3.init(r+1);
   bit4.init(r);
   set<pair<int, int>> st1, st2, st3, st4;
   auto insert2=[&](int x, int y){
      st2.emplace(x, y);
      st2.emplace(x, y+1);
      st2.emplace(x+1, y);
      st2.emplace(x+1, y+1);
   };
   auto insert3=[&](int x, int y){
      st3.emplace(x, y);
      st3.emplace(x+1, y);
   };
   auto insert4=[&](int x, int y){
      st4.emplace(x, y);
      st4.emplace(x, y+1);
   };
   auto insert=[&](int x, int y){
      st1.emplace(x, y);
      insert2(x, y);
      insert3(x, y);
      insert4(x, y);
   };
   insert(sr, sc);
   for (int i=0; i<M; ++i){
      if (S[i]=='N') --sr;
      if (S[i]=='S') ++sr;
      if (S[i]=='E') ++sc;
      if (S[i]=='W') --sc;
      insert(sr, sc);
   }
   for (auto &i:st1) bit1.fake_update(i.first, i.second);
   for (auto &i:st2) bit2.fake_update(i.first, i.second);
   for (auto &i:st3) bit3.fake_update(i.first, i.second);
   for (auto &i:st4) bit4.fake_update(i.first, i.second);
   bit1.compress();
   bit2.compress();
   bit3.compress();
   bit4.compress();
   for (auto &i:st1) bit1.update(i.first, i.second, 1);
   for (auto &i:st2) bit2.update(i.first, i.second, 1);
   for (auto &i:st3) bit3.update(i.first, i.second, 1);
   for (auto &i:st4) bit4.update(i.first, i.second, 1);
}

int colour(int ar, int ac, int br, int bc) {
   int V=(br-ar+1)*2+(bc-ac+1)*2+bit2.get(ar+1, ac+1, br, bc);
   int E=(br-ar+1)*2+(bc-ac+1)*2+bit3.get(ar+1, ac, br, bc)+bit4.get(ar, ac+1, br, bc);
   int CC=1;
   int cnt_out;
   if (ar==br || ac==bc) cnt_out=bit1.get(ar, ac, br, bc);
   else cnt_out=bit1.get(ar, ac, ar, bc-1)+bit1.get(ar, bc, br-1, bc)+bit1.get(br, ac+1, br, bc)+bit1.get(ar+1, ac, br, ac);
   int cnt_in=bit1.get(ar+1, ac+1, br-1, bc-1);
   if (cnt_in && !cnt_out) ++CC;
   int F=cnt_in+cnt_out;
   // cerr << V << ' ' << E << ' ' << CC << ' ' << F << '\n';
   return E-V+CC-F;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19292 KB Output is correct
2 Correct 11 ms 19500 KB Output is correct
3 Correct 7 ms 19292 KB Output is correct
4 Correct 8 ms 19288 KB Output is correct
5 Correct 13 ms 19544 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 5 ms 19236 KB Output is correct
9 Correct 5 ms 19036 KB Output is correct
10 Correct 6 ms 19240 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 19548 KB Output is correct
13 Correct 14 ms 19904 KB Output is correct
14 Correct 16 ms 20068 KB Output is correct
15 Correct 5 ms 19228 KB Output is correct
16 Correct 5 ms 19036 KB Output is correct
17 Correct 5 ms 19036 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 288 ms 44012 KB Output is correct
4 Correct 545 ms 58424 KB Output is correct
5 Correct 487 ms 58208 KB Output is correct
6 Correct 422 ms 50080 KB Output is correct
7 Correct 474 ms 50432 KB Output is correct
8 Correct 77 ms 22880 KB Output is correct
9 Correct 527 ms 58336 KB Output is correct
10 Correct 515 ms 58224 KB Output is correct
11 Correct 484 ms 50440 KB Output is correct
12 Correct 370 ms 55228 KB Output is correct
13 Correct 412 ms 58404 KB Output is correct
14 Correct 466 ms 58028 KB Output is correct
15 Correct 325 ms 50092 KB Output is correct
16 Correct 318 ms 49084 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19228 KB Output is correct
2 Correct 853 ms 122412 KB Output is correct
3 Correct 488 ms 136136 KB Output is correct
4 Correct 740 ms 135440 KB Output is correct
5 Correct 489 ms 110400 KB Output is correct
6 Correct 232 ms 59948 KB Output is correct
7 Correct 354 ms 70864 KB Output is correct
8 Correct 361 ms 52980 KB Output is correct
9 Correct 443 ms 52036 KB Output is correct
10 Correct 125 ms 40696 KB Output is correct
11 Correct 332 ms 53988 KB Output is correct
12 Correct 813 ms 122420 KB Output is correct
13 Correct 444 ms 136336 KB Output is correct
14 Correct 649 ms 135436 KB Output is correct
15 Correct 446 ms 110316 KB Output is correct
16 Correct 193 ms 56984 KB Output is correct
17 Correct 383 ms 78236 KB Output is correct
18 Correct 909 ms 150660 KB Output is correct
19 Correct 648 ms 133352 KB Output is correct
20 Correct 698 ms 139948 KB Output is correct
21 Correct 337 ms 52980 KB Output is correct
22 Correct 330 ms 52056 KB Output is correct
23 Correct 115 ms 40900 KB Output is correct
24 Correct 237 ms 53964 KB Output is correct
25 Correct 826 ms 122416 KB Output is correct
26 Correct 447 ms 136600 KB Output is correct
27 Correct 675 ms 135876 KB Output is correct
28 Correct 447 ms 110316 KB Output is correct
29 Correct 207 ms 57200 KB Output is correct
30 Correct 396 ms 78232 KB Output is correct
31 Correct 937 ms 150872 KB Output is correct
32 Correct 678 ms 133412 KB Output is correct
33 Correct 705 ms 139916 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19292 KB Output is correct
2 Correct 11 ms 19500 KB Output is correct
3 Correct 7 ms 19292 KB Output is correct
4 Correct 8 ms 19288 KB Output is correct
5 Correct 13 ms 19544 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 5 ms 19236 KB Output is correct
9 Correct 5 ms 19036 KB Output is correct
10 Correct 6 ms 19240 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 19548 KB Output is correct
13 Correct 14 ms 19904 KB Output is correct
14 Correct 16 ms 20068 KB Output is correct
15 Correct 5 ms 19228 KB Output is correct
16 Correct 5 ms 19036 KB Output is correct
17 Correct 5 ms 19036 KB Output is correct
18 Correct 927 ms 51744 KB Output is correct
19 Correct 328 ms 23892 KB Output is correct
20 Correct 240 ms 22740 KB Output is correct
21 Correct 271 ms 23132 KB Output is correct
22 Correct 292 ms 23324 KB Output is correct
23 Correct 345 ms 23748 KB Output is correct
24 Correct 320 ms 23024 KB Output is correct
25 Correct 308 ms 23192 KB Output is correct
26 Correct 325 ms 23680 KB Output is correct
27 Correct 521 ms 44204 KB Output is correct
28 Correct 458 ms 34000 KB Output is correct
29 Correct 529 ms 42340 KB Output is correct
30 Correct 936 ms 83048 KB Output is correct
31 Correct 10 ms 19292 KB Output is correct
32 Correct 701 ms 48616 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19292 KB Output is correct
2 Correct 11 ms 19500 KB Output is correct
3 Correct 7 ms 19292 KB Output is correct
4 Correct 8 ms 19288 KB Output is correct
5 Correct 13 ms 19544 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 5 ms 19236 KB Output is correct
9 Correct 5 ms 19036 KB Output is correct
10 Correct 6 ms 19240 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 19548 KB Output is correct
13 Correct 14 ms 19904 KB Output is correct
14 Correct 16 ms 20068 KB Output is correct
15 Correct 5 ms 19228 KB Output is correct
16 Correct 5 ms 19036 KB Output is correct
17 Correct 5 ms 19036 KB Output is correct
18 Correct 927 ms 51744 KB Output is correct
19 Correct 328 ms 23892 KB Output is correct
20 Correct 240 ms 22740 KB Output is correct
21 Correct 271 ms 23132 KB Output is correct
22 Correct 292 ms 23324 KB Output is correct
23 Correct 345 ms 23748 KB Output is correct
24 Correct 320 ms 23024 KB Output is correct
25 Correct 308 ms 23192 KB Output is correct
26 Correct 325 ms 23680 KB Output is correct
27 Correct 521 ms 44204 KB Output is correct
28 Correct 458 ms 34000 KB Output is correct
29 Correct 529 ms 42340 KB Output is correct
30 Correct 936 ms 83048 KB Output is correct
31 Correct 10 ms 19292 KB Output is correct
32 Correct 701 ms 48616 KB Output is correct
33 Correct 853 ms 122412 KB Output is correct
34 Correct 488 ms 136136 KB Output is correct
35 Correct 740 ms 135440 KB Output is correct
36 Correct 489 ms 110400 KB Output is correct
37 Correct 232 ms 59948 KB Output is correct
38 Correct 354 ms 70864 KB Output is correct
39 Correct 361 ms 52980 KB Output is correct
40 Correct 443 ms 52036 KB Output is correct
41 Correct 125 ms 40696 KB Output is correct
42 Correct 332 ms 53988 KB Output is correct
43 Correct 813 ms 122420 KB Output is correct
44 Correct 444 ms 136336 KB Output is correct
45 Correct 649 ms 135436 KB Output is correct
46 Correct 446 ms 110316 KB Output is correct
47 Correct 193 ms 56984 KB Output is correct
48 Correct 383 ms 78236 KB Output is correct
49 Correct 909 ms 150660 KB Output is correct
50 Correct 648 ms 133352 KB Output is correct
51 Correct 698 ms 139948 KB Output is correct
52 Correct 337 ms 52980 KB Output is correct
53 Correct 330 ms 52056 KB Output is correct
54 Correct 115 ms 40900 KB Output is correct
55 Correct 237 ms 53964 KB Output is correct
56 Correct 826 ms 122416 KB Output is correct
57 Correct 447 ms 136600 KB Output is correct
58 Correct 675 ms 135876 KB Output is correct
59 Correct 447 ms 110316 KB Output is correct
60 Correct 207 ms 57200 KB Output is correct
61 Correct 396 ms 78232 KB Output is correct
62 Correct 937 ms 150872 KB Output is correct
63 Correct 678 ms 133412 KB Output is correct
64 Correct 705 ms 139916 KB Output is correct
65 Correct 288 ms 44012 KB Output is correct
66 Correct 545 ms 58424 KB Output is correct
67 Correct 487 ms 58208 KB Output is correct
68 Correct 422 ms 50080 KB Output is correct
69 Correct 474 ms 50432 KB Output is correct
70 Correct 77 ms 22880 KB Output is correct
71 Correct 527 ms 58336 KB Output is correct
72 Correct 515 ms 58224 KB Output is correct
73 Correct 484 ms 50440 KB Output is correct
74 Correct 370 ms 55228 KB Output is correct
75 Correct 412 ms 58404 KB Output is correct
76 Correct 466 ms 58028 KB Output is correct
77 Correct 325 ms 50092 KB Output is correct
78 Correct 318 ms 49084 KB Output is correct
79 Correct 702 ms 56564 KB Output is correct
80 Correct 845 ms 55468 KB Output is correct
81 Correct 528 ms 44272 KB Output is correct
82 Correct 632 ms 57244 KB Output is correct
83 Correct 1318 ms 125996 KB Output is correct
84 Correct 864 ms 139736 KB Output is correct
85 Correct 1234 ms 138896 KB Output is correct
86 Correct 936 ms 113680 KB Output is correct
87 Correct 597 ms 60296 KB Output is correct
88 Correct 767 ms 81692 KB Output is correct
89 Correct 1308 ms 154132 KB Output is correct
90 Correct 1196 ms 136816 KB Output is correct
91 Correct 1052 ms 143280 KB Output is correct