제출 #146287

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
146287	2019-08-23 09:54:15	TadijaSebez	무지개나라 (APIO17_rainbow)	C++11	100 / 100	845 ms	149024 KiB

rainbow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
  v[0].pb(p);
  v[1].pb(p);if(p.x!=1) v[1].pb(p-pt(1,0));
  v[2].pb(p);if(p.y!=1) v[2].pb(p-pt(0,1));
  v[3].pb(p);if(p.x!=1) v[3].pb(p-pt(1,0));if(p.y!=1) v[3].pb(p-pt(0,1));if(min(p.x,p.y)!=1) v[3].pb(p-pt(1,1));
}
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
const int N=200050;
const int M=900050;
const int H=20*M;
int ls[H],rs[H],tsz,sum[H],n,m,root[4][N];
void Set(int p, int &c, int ss, int se, int qi)
{
  c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
  if(ss==se) return;
  int mid=ss+se>>1;
  if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

컴파일 시 표준 에러 (stderr) 메시지

rainbow.cpp: In function 'void Set(int, int&, int, int, int)':
rainbow.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'int Get(int, int, int, int, int, int)':
rainbow.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
rainbow.cpp: In function 'void Build()':
rainbow.cpp:50:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(;k<v[i].size() && v[i][k].x==j;k++) Set(root[i][j],root[i][j],1,N,v[i][k].y);
         ~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26