답안 #59652 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59652	2018-07-22T20:50:35 Z	duality	무지개나라 (APIO17_rainbow)	C++11	47 / 100	1380 ms	127368 KB

rainbow

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "rainbow.h"

int r,c;
int lx,rx,ly,ry;
vi tree[4][1 << 19];
int sorted[4][1 << 19];
int update(int s,int e,int ay,int ax,int i,int t) {
    if ((s > ay) || (e < ay)) return 0;
    else if (s == e) {
        tree[t][i].pb(ax);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,ay,ax,2*i+1,t);
    update(mid+1,e,ay,ax,2*i+2,t);
    tree[t][i].pb(ax);
    return 0;
}
int query(int s,int e,int qys,int qye,int qxs,int qxe,int i,int t) {
    if ((qys > qye) || (qxs > qxe)) return 0;
    else if ((s > qye) || (e < qys)) return 0;
    else if ((s >= qys) && (e <= qye)) {
        if (!sorted[t][i]) sort(tree[t][i].begin(),tree[t][i].end()),sorted[t][i] = 1;
        return upper_bound(tree[t][i].begin(),tree[t][i].end(),qxe) \
             - lower_bound(tree[t][i].begin(),tree[t][i].end(),qxs);
    }

    int mid = (s+e) / 2;
    return query(s,mid,qys,qye,qxs,qxe,2*i+1,t)+query(mid+1,e,qys,qye,qxs,qxe,2*i+2,t);
}
vpii p1,p2,p3,p4;
void init(int R,int C,int sr,int sc,int M,char *S) {
    int i;
    r = R,c = C;
    sr--,sc--;
    lx = rx = sc,ly = ry = sr;
    p1.pb(mp(sr+1,sc+1));
    p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1));
    p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc));
    p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc));
    for (i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
        lx = min(lx,sc),rx = max(rx,sc);
        ly = min(lx,sr),ry = max(ry,sr);
        p1.pb(mp(sr+1,sc+1));
        p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1));
        p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc));
        p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc));
    }
    sort(p1.begin(),p1.end());
    p1.resize(unique(p1.begin(),p1.end())-p1.begin());
    sort(p2.begin(),p2.end());
    p2.resize(unique(p2.begin(),p2.end())-p2.begin());
    sort(p3.begin(),p3.end());
    p3.resize(unique(p3.begin(),p3.end())-p3.begin());
    sort(p4.begin(),p4.end());
    p4.resize(unique(p4.begin(),p4.end())-p4.begin());
    for (i = 0; i < p1.size(); i++) update(0,r,p1[i].first,p1[i].second,0,0);
    for (i = 0; i < p2.size(); i++) update(0,r,p2[i].first,p2[i].second,0,1);
    for (i = 0; i < p3.size(); i++) update(0,r,p3[i].first,p3[i].second,0,2);
    for (i = 0; i < p4.size(); i++) update(0,r,p4[i].first,p4[i].second,0,3);
}

int colour(int ar,int ac,int br,int bc) {
    ar--,ac--,br--,bc--;
    LLI ans = 0;
    ans += (LLI) (br-ar+1)*(bc-ac+1)-query(0,r,ar+1,br+1,ac+1,bc+1,0,0);
    ans -= (LLI) (br-ar)*(bc-ac+1)-query(0,r,ar+1,br,ac+1,bc+1,0,1);
    ans -= (LLI) (br-ar+1)*(bc-ac)-query(0,r,ar+1,br+1,ac+1,bc,0,2);
    ans += (LLI) (br-ar)*(bc-ac)-query(0,r,ar+1,br,ac+1,bc,0,3);
    if ((ar < ly) && (br > ry) && (ac < lx) && (bc > rx)) ans++;
    return ans;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p1.size(); i++) update(0,r,p1[i].first,p1[i].second,0,0);
                 ~~^~~~~~~~~~~
rainbow.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p2.size(); i++) update(0,r,p2[i].first,p2[i].second,0,1);
                 ~~^~~~~~~~~~~
rainbow.cpp:120:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p3.size(); i++) update(0,r,p3[i].first,p3[i].second,0,2);
                 ~~^~~~~~~~~~~
rainbow.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p4.size(); i++) update(0,r,p4[i].first,p4[i].second,0,3);
                 ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	49656 KB	Output is correct
2	Correct	49 ms	49892 KB	Output is correct
3	Correct	45 ms	49892 KB	Output is correct
4	Correct	48 ms	49892 KB	Output is correct
5	Correct	52 ms	50288 KB	Output is correct
6	Correct	45 ms	50288 KB	Output is correct
7	Correct	45 ms	50288 KB	Output is correct
8	Correct	45 ms	50288 KB	Output is correct
9	Correct	46 ms	50288 KB	Output is correct
10	Correct	45 ms	50288 KB	Output is correct
11	Correct	55 ms	50288 KB	Output is correct
12	Correct	58 ms	50288 KB	Output is correct
13	Correct	54 ms	50304 KB	Output is correct
14	Correct	63 ms	50696 KB	Output is correct
15	Correct	44 ms	50696 KB	Output is correct
16	Correct	44 ms	50696 KB	Output is correct
17	Correct	44 ms	50696 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	50696 KB	Output is correct
2	Correct	44 ms	50696 KB	Output is correct
3	Correct	251 ms	59740 KB	Output is correct
4	Correct	304 ms	66304 KB	Output is correct
5	Correct	298 ms	66348 KB	Output is correct
6	Correct	352 ms	66348 KB	Output is correct
7	Correct	332 ms	66348 KB	Output is correct
8	Correct	198 ms	66348 KB	Output is correct
9	Correct	366 ms	66348 KB	Output is correct
10	Correct	337 ms	66348 KB	Output is correct
11	Correct	331 ms	66348 KB	Output is correct
12	Correct	213 ms	66348 KB	Output is correct
13	Correct	309 ms	66424 KB	Output is correct
14	Correct	278 ms	66424 KB	Output is correct
15	Correct	244 ms	66424 KB	Output is correct
16	Correct	281 ms	66424 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	50696 KB	Output is correct
2	Correct	356 ms	109044 KB	Output is correct
3	Correct	505 ms	127224 KB	Output is correct
4	Correct	513 ms	127224 KB	Output is correct
5	Correct	358 ms	127224 KB	Output is correct
6	Correct	206 ms	127224 KB	Output is correct
7	Correct	231 ms	127224 KB	Output is correct
8	Correct	205 ms	127224 KB	Output is correct
9	Correct	172 ms	127224 KB	Output is correct
10	Correct	163 ms	127224 KB	Output is correct
11	Correct	257 ms	127224 KB	Output is correct
12	Correct	325 ms	127224 KB	Output is correct
13	Correct	556 ms	127240 KB	Output is correct
14	Correct	501 ms	127240 KB	Output is correct
15	Correct	324 ms	127240 KB	Output is correct
16	Correct	180 ms	127240 KB	Output is correct
17	Correct	252 ms	127240 KB	Output is correct
18	Correct	392 ms	127240 KB	Output is correct
19	Correct	440 ms	127240 KB	Output is correct
20	Correct	459 ms	127240 KB	Output is correct
21	Correct	218 ms	127240 KB	Output is correct
22	Correct	220 ms	127240 KB	Output is correct
23	Correct	190 ms	127240 KB	Output is correct
24	Correct	274 ms	127240 KB	Output is correct
25	Correct	413 ms	127240 KB	Output is correct
26	Correct	519 ms	127368 KB	Output is correct
27	Correct	406 ms	127368 KB	Output is correct
28	Correct	356 ms	127368 KB	Output is correct
29	Correct	188 ms	127368 KB	Output is correct
30	Correct	218 ms	127368 KB	Output is correct
31	Correct	355 ms	127368 KB	Output is correct
32	Correct	435 ms	127368 KB	Output is correct
33	Correct	413 ms	127368 KB	Output is correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	49656 KB	Output is correct
2	Correct	49 ms	49892 KB	Output is correct
3	Correct	45 ms	49892 KB	Output is correct
4	Correct	48 ms	49892 KB	Output is correct
5	Correct	52 ms	50288 KB	Output is correct
6	Correct	45 ms	50288 KB	Output is correct
7	Correct	45 ms	50288 KB	Output is correct
8	Correct	45 ms	50288 KB	Output is correct
9	Correct	46 ms	50288 KB	Output is correct
10	Correct	45 ms	50288 KB	Output is correct
11	Correct	55 ms	50288 KB	Output is correct
12	Correct	58 ms	50288 KB	Output is correct
13	Correct	54 ms	50304 KB	Output is correct
14	Correct	63 ms	50696 KB	Output is correct
15	Correct	44 ms	50696 KB	Output is correct
16	Correct	44 ms	50696 KB	Output is correct
17	Correct	44 ms	50696 KB	Output is correct
18	Correct	1380 ms	127368 KB	Output is correct
19	Correct	320 ms	127368 KB	Output is correct
20	Correct	309 ms	127368 KB	Output is correct
21	Correct	314 ms	127368 KB	Output is correct
22	Correct	384 ms	127368 KB	Output is correct
23	Correct	253 ms	127368 KB	Output is correct
24	Correct	302 ms	127368 KB	Output is correct
25	Correct	329 ms	127368 KB	Output is correct
26	Correct	390 ms	127368 KB	Output is correct
27	Correct	736 ms	127368 KB	Output is correct
28	Incorrect	610 ms	127368 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	49656 KB	Output is correct
2	Correct	49 ms	49892 KB	Output is correct
3	Correct	45 ms	49892 KB	Output is correct
4	Correct	48 ms	49892 KB	Output is correct
5	Correct	52 ms	50288 KB	Output is correct
6	Correct	45 ms	50288 KB	Output is correct
7	Correct	45 ms	50288 KB	Output is correct
8	Correct	45 ms	50288 KB	Output is correct
9	Correct	46 ms	50288 KB	Output is correct
10	Correct	45 ms	50288 KB	Output is correct
11	Correct	55 ms	50288 KB	Output is correct
12	Correct	58 ms	50288 KB	Output is correct
13	Correct	54 ms	50304 KB	Output is correct
14	Correct	63 ms	50696 KB	Output is correct
15	Correct	44 ms	50696 KB	Output is correct
16	Correct	44 ms	50696 KB	Output is correct
17	Correct	44 ms	50696 KB	Output is correct
18	Correct	1380 ms	127368 KB	Output is correct
19	Correct	320 ms	127368 KB	Output is correct
20	Correct	309 ms	127368 KB	Output is correct
21	Correct	314 ms	127368 KB	Output is correct
22	Correct	384 ms	127368 KB	Output is correct
23	Correct	253 ms	127368 KB	Output is correct
24	Correct	302 ms	127368 KB	Output is correct
25	Correct	329 ms	127368 KB	Output is correct
26	Correct	390 ms	127368 KB	Output is correct
27	Correct	736 ms	127368 KB	Output is correct
28	Incorrect	610 ms	127368 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #59652

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 12.0 / 12.0

Subtask #3 24.0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
12.0 / 12.0

Subtask #3
24.0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0