Submission #304014

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
304014	2020-09-21 00:23:48	arnold518	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2492 ms	695688 KiB

circle_selection

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 <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 6e5;
 
struct Circle
{
  ll x, y, r; int p;
};
 
int N;
Circle A[MAXN+10], B[MAXN+10];
vector<ll> xcomp, ycomp;
bool vis[MAXN+10];
 
int getycomp(int x) { return lower_bound(ycomp.begin(), ycomp.end(), x)-ycomp.begin()+1; }
 
struct Node
{
  ll x, y;
  int par;
  Node() : x(0), y(0), par(0) {}
  Node(int x, int y) : x(x), y(y), par(0) {}
  bool operator < (const Node &p) { return x<p.x; }
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

circle_selection.cpp: In function 'int Find(int, std::vector<Node>&)':
circle_selection.cpp:33:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(x>=V.size()) return x;
      |     ~^~~~~~~~~~
circle_selection.cpp: In member function 'void SEG::push(int, int, int, int, ll, int)':
circle_selection.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In member function 'void SEG::init(int, int, int)':
circle_selection.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int i=0; i<tree[node].size(); i++) tree[node][i].par=i;
      |                 ~^~~~~~~~~~~~~~~~~~
circle_selection.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0; i<tree[node].size(); i++) tree[node][i].par=i;
      |                ~^~~~~~~~~~~~~~~~~~
circle_selection.cpp: In member function 'void SEG::pop(int, int, int, int, int, ll, ll, std::vector<int>&)':
circle_selection.cpp:72:116: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int i=Find(lower_bound(tree[node].begin(), tree[node].end(), Node(pl, 0))-tree[node].begin(), tree[node]); i<tree[node].size() && tree[node][i].x<=pr; i=Find(i+1, tree[node]))
      |                                                                                                                   ~^~~~~~~~~~~~~~~~~~
circle_selection.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int mid=tl+tr>>1;
      |           ~~^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
circle_selection.cpp:97:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13