Submission #286371

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
286371	2020-08-30 10:37:52	TadijaSebez	Constellation 3 (JOI20_constellation3)	C++11	35 / 100	1589 ms	132060 KiB

constellation3

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;
#define pii pair<int,int>
#define ll long long
#define pb push_back
const int N=200050;
const int L=20;
int a[N],lgs[N],n;
pii rmq[N][L];
pii Get(int l,int r){
  int k=lgs[r-l+1];
  return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
pii GetRng(int x,int y){
  int top=x,bot=1,mid,L=0,R=n+1;
  while(top>=bot){
    mid=top+bot>>1;
    if(Get(mid,x).first>=y)L=mid,bot=mid+1;
    else top=mid-1;
  }
  top=n,bot=x;
  while(top>=bot){
    mid=top+bot>>1;
    if(Get(x,mid).first>=y)R=mid,top=mid-1;
    else bot=mid+1;
  }
  return {L,R};
}
int x[N],y[N],c[N],ord[N];
unordered_map<ll,vector<int>> stars;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

constellation3.cpp: In function 'std::pair<int, int> GetRng(int, int)':
constellation3.cpp:17:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp:23:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   mid=top+bot>>1;
      |       ~~~^~~~
constellation3.cpp: In function 'int Check(int, int, int)':
constellation3.cpp:40:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   if(j<bit[i].size()&&bit[i][j]<=r)return 1;
      |      ~^~~~~~~~~~~~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:91:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |    rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                        ~^~
constellation3.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:87:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),rmq[i][0]={a[i],i};//,idx[a[i]].pb(i);
      |                       ~~~~~^~~~~~~~~~~~
constellation3.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  scanf("%i",&m);
      |  ~~~~~^~~~~~~~~
constellation3.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |   scanf("%i %i %i",&x[i],&y[i],&c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 65