oj.uz

Submission #578568

# Submission time Handle Problem Language Result Execution time Memory
578568 2022-06-17T10:04:24 Z jiahng Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1697 ms 622540 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
// #define ll int
//#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 120001
#define INF 1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int R,C;

struct node{
    int s,e,m;
    int val = 0;
    node *l,*r;
    node(int ss,int ee){
        s = ss; e = ee; m = (s + e) / 2;
    }
    void init(){
        if (s != e){
            l = new node(s,m); r = new node(m+1,e);
            l->init(); r->init();
        }
    }
    void upd(int p,int v, node *ref){
        val += v;
        if (s == e) return;
        else if (p > m){
            l = ref->l;
            r = new node(m+1,e); r->val = ref->r->val; r->upd(p,v,ref->r);
        }else{
            r = ref->r;
            l = new node(s,m); l->val = ref->l->val; l->upd(p,v,ref->l);
        }
    }
    int qry(int a,int b){
        if (a <= s && e <= b) return val;
        else if (a > e || s > b) return 0;
        return l->qry(a,b) + r->qry(a,b);
    }
};
struct seg2D{
    vector <node*> roots;
    seg2D(int N,int M,vpi &v){
        node *root = new node(1,M); root->init();
        roots.pb(root);
        
        sort(all(v)); v.erase(unique(all(v)),v.end()); int ptr = 0;
        FOR(i,1,N){
           while(ptr < v.size() && v[ptr].f == i){
			   node *newroot = new node(1,M); newroot->val = root->val;
			   newroot->upd(v[ptr].s,1,root); ptr++;
			   root = newroot;
		   }
           roots.pb(root); 
        }
    }
    int qry(int a,int b,int c,int d){
        return roots[b]->qry(c,d) - roots[a-1]->qry(c,d);
    }
}*lakeseg, *horseg, *vertseg, *cornerseg;
set <pi> st;
void init(int R, int C, int sr, int sc, int M, char *S) {
    int x=sr,y=sc;
    vpi lake,hor,vert,corner;
    lake.pb(pi(x,y));
    FOR(dx,0,1) FOR(dy,0,1) corner.pb(pi(x+dx,y+dy));
    hor.pb(pi(x,y)); hor.pb(pi(x+1,y));
    vert.pb(pi(x,y)); vert.pb(pi(x, y+1));
    FOR(i,0,M-1){
        if (S[i] == 'S') x++;
        else if (S[i] == 'N') x--;
        else if (S[i] == 'E') y++;
        else if (S[i] == 'W') y--;
        lake.pb(pi(x,y));
        FOR(dx,0,1) FOR(dy,0,1) corner.pb(pi(x+dx,y+dy));
		hor.pb(pi(x,y)); hor.pb(pi(x+1,y));
		vert.pb(pi(x,y)); vert.pb(pi(x, y+1));
    }
    lakeseg = new seg2D(R+1,C+1,lake);
    //cout << lakeseg->qry(2,3,2,3);
    //cout.flush();
    cornerseg = new seg2D(R+1,C+1,corner);
    horseg = new seg2D(R+1,C+1,hor);
    vertseg = new seg2D(R+1,C+1,vert);
}

int colour(int ar, int ac, int br, int bc) {
   int edges = horseg->qry(ar+1,br,ac,bc) + vertseg->qry(ar,br,ac+1,bc) + 2 * (br - ar + 1 + bc - ac + 1);
   int vertices = cornerseg->qry(ar+1,br,ac+1,bc) + 2 * (br - ar + 2 + bc - ac + 2) - 4;
   int touch = lakeseg->qry(ar,ar,ac,bc) + lakeseg->qry(br,br,ac,bc);
   touch += lakeseg->qry(ar,br,ac,ac) + lakeseg->qry(ar,br,bc,bc);
   int numlake = lakeseg->qry(ar,br,ac,bc); 
   //cout << horseg->qry(ar,br,ac+1,bc) << ' ' << vertseg->qry(ar+1,br,ac,bc) << ' ' << 2 * (br - ar + 1 + bc - ac + 1) << ' ' <<  edges << ' ' << vertices << '\n';
   return edges - vertices + 1 - numlake + (!touch && numlake);
}

Compilation message

rainbow.cpp: In constructor 'seg2D::seg2D(int, int, vpi&)':
rainbow.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |            while(ptr < v.size() && v[ptr].f == i){
      |                  ~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 5 ms 1984 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 4 ms 960 KB Output is correct
12 Correct 4 ms 1620 KB Output is correct
13 Correct 6 ms 2960 KB Output is correct
14 Correct 8 ms 3668 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1394 ms 395316 KB Output is correct
4 Correct 1697 ms 610108 KB Output is correct
5 Correct 1662 ms 605980 KB Output is correct
6 Correct 1369 ms 485848 KB Output is correct
7 Correct 1403 ms 478808 KB Output is correct
8 Correct 797 ms 83792 KB Output is correct
9 Correct 1634 ms 610184 KB Output is correct
10 Correct 1664 ms 605920 KB Output is correct
11 Correct 1441 ms 485616 KB Output is correct
12 Correct 772 ms 572940 KB Output is correct
13 Correct 811 ms 609872 KB Output is correct
14 Correct 827 ms 605768 KB Output is correct
15 Correct 729 ms 486176 KB Output is correct
16 Correct 1383 ms 455440 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 599 ms 617364 KB Output is correct
3 Correct 548 ms 615620 KB Output is correct
4 Correct 590 ms 617840 KB Output is correct
5 Correct 462 ms 484764 KB Output is correct
6 Correct 232 ms 188208 KB Output is correct
7 Correct 319 ms 287280 KB Output is correct
8 Correct 478 ms 434692 KB Output is correct
9 Correct 464 ms 374480 KB Output is correct
10 Correct 110 ms 74392 KB Output is correct
11 Correct 291 ms 242060 KB Output is correct
12 Correct 679 ms 617328 KB Output is correct
13 Correct 591 ms 615656 KB Output is correct
14 Correct 570 ms 617824 KB Output is correct
15 Correct 456 ms 484732 KB Output is correct
16 Correct 217 ms 169264 KB Output is correct
17 Correct 323 ms 288344 KB Output is correct
18 Correct 637 ms 618500 KB Output is correct
19 Correct 636 ms 622116 KB Output is correct
20 Correct 655 ms 621784 KB Output is correct
21 Correct 542 ms 434532 KB Output is correct
22 Correct 468 ms 374424 KB Output is correct
23 Correct 126 ms 74416 KB Output is correct
24 Correct 302 ms 242088 KB Output is correct
25 Correct 628 ms 617376 KB Output is correct
26 Correct 615 ms 615636 KB Output is correct
27 Correct 596 ms 617904 KB Output is correct
28 Correct 463 ms 484796 KB Output is correct
29 Correct 225 ms 169264 KB Output is correct
30 Correct 324 ms 288344 KB Output is correct
31 Correct 675 ms 618640 KB Output is correct
32 Correct 572 ms 622120 KB Output is correct
33 Correct 579 ms 621784 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 5 ms 1984 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 4 ms 960 KB Output is correct
12 Correct 4 ms 1620 KB Output is correct
13 Correct 6 ms 2960 KB Output is correct
14 Correct 8 ms 3668 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1046 ms 165512 KB Output is correct
19 Correct 306 ms 11248 KB Output is correct
20 Correct 192 ms 4756 KB Output is correct
21 Correct 234 ms 5836 KB Output is correct
22 Correct 250 ms 7188 KB Output is correct
23 Correct 307 ms 10928 KB Output is correct
24 Correct 206 ms 5372 KB Output is correct
25 Correct 236 ms 6720 KB Output is correct
26 Correct 263 ms 7780 KB Output is correct
27 Correct 551 ms 135064 KB Output is correct
28 Correct 440 ms 69520 KB Output is correct
29 Correct 531 ms 124228 KB Output is correct
30 Correct 841 ms 318396 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 785 ms 136628 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 5 ms 1984 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 5 ms 2388 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 4 ms 960 KB Output is correct
12 Correct 4 ms 1620 KB Output is correct
13 Correct 6 ms 2960 KB Output is correct
14 Correct 8 ms 3668 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1046 ms 165512 KB Output is correct
19 Correct 306 ms 11248 KB Output is correct
20 Correct 192 ms 4756 KB Output is correct
21 Correct 234 ms 5836 KB Output is correct
22 Correct 250 ms 7188 KB Output is correct
23 Correct 307 ms 10928 KB Output is correct
24 Correct 206 ms 5372 KB Output is correct
25 Correct 236 ms 6720 KB Output is correct
26 Correct 263 ms 7780 KB Output is correct
27 Correct 551 ms 135064 KB Output is correct
28 Correct 440 ms 69520 KB Output is correct
29 Correct 531 ms 124228 KB Output is correct
30 Correct 841 ms 318396 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 785 ms 136628 KB Output is correct
33 Correct 599 ms 617364 KB Output is correct
34 Correct 548 ms 615620 KB Output is correct
35 Correct 590 ms 617840 KB Output is correct
36 Correct 462 ms 484764 KB Output is correct
37 Correct 232 ms 188208 KB Output is correct
38 Correct 319 ms 287280 KB Output is correct
39 Correct 478 ms 434692 KB Output is correct
40 Correct 464 ms 374480 KB Output is correct
41 Correct 110 ms 74392 KB Output is correct
42 Correct 291 ms 242060 KB Output is correct
43 Correct 679 ms 617328 KB Output is correct
44 Correct 591 ms 615656 KB Output is correct
45 Correct 570 ms 617824 KB Output is correct
46 Correct 456 ms 484732 KB Output is correct
47 Correct 217 ms 169264 KB Output is correct
48 Correct 323 ms 288344 KB Output is correct
49 Correct 637 ms 618500 KB Output is correct
50 Correct 636 ms 622116 KB Output is correct
51 Correct 655 ms 621784 KB Output is correct
52 Correct 542 ms 434532 KB Output is correct
53 Correct 468 ms 374424 KB Output is correct
54 Correct 126 ms 74416 KB Output is correct
55 Correct 302 ms 242088 KB Output is correct
56 Correct 628 ms 617376 KB Output is correct
57 Correct 615 ms 615636 KB Output is correct
58 Correct 596 ms 617904 KB Output is correct
59 Correct 463 ms 484796 KB Output is correct
60 Correct 225 ms 169264 KB Output is correct
61 Correct 324 ms 288344 KB Output is correct
62 Correct 675 ms 618640 KB Output is correct
63 Correct 572 ms 622120 KB Output is correct
64 Correct 579 ms 621784 KB Output is correct
65 Correct 1394 ms 395316 KB Output is correct
66 Correct 1697 ms 610108 KB Output is correct
67 Correct 1662 ms 605980 KB Output is correct
68 Correct 1369 ms 485848 KB Output is correct
69 Correct 1403 ms 478808 KB Output is correct
70 Correct 797 ms 83792 KB Output is correct
71 Correct 1634 ms 610184 KB Output is correct
72 Correct 1664 ms 605920 KB Output is correct
73 Correct 1441 ms 485616 KB Output is correct
74 Correct 772 ms 572940 KB Output is correct
75 Correct 811 ms 609872 KB Output is correct
76 Correct 827 ms 605768 KB Output is correct
77 Correct 729 ms 486176 KB Output is correct
78 Correct 1383 ms 455440 KB Output is correct
79 Correct 1690 ms 435012 KB Output is correct
80 Correct 1585 ms 374820 KB Output is correct
81 Correct 607 ms 76416 KB Output is correct
82 Correct 1008 ms 242484 KB Output is correct
83 Correct 1539 ms 617784 KB Output is correct
84 Correct 1335 ms 616112 KB Output is correct
85 Correct 1407 ms 618312 KB Output is correct
86 Correct 1273 ms 485556 KB Output is correct
87 Correct 979 ms 169928 KB Output is correct
88 Correct 1088 ms 288772 KB Output is correct
89 Correct 1328 ms 618852 KB Output is correct
90 Correct 1559 ms 622540 KB Output is correct
91 Correct 1262 ms 622192 KB Output is correct