Submission #154799

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
154799	2019-09-24 17:42:09	TadijaSebez	Matryoshka (JOI16_matryoshka)	C++11	100 / 100	998 ms	77308 KiB

matryoshka

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 pb push_back
const int N=200050;
const int M=N*60;
const int lim=1e9;
int a[N],b[N],x[N],y[N];
int uid[N],qid[N],ans[N];
int ls[M],rs[M],tsz,root[2],sum[M];
void Set(int &c, int ss, int se, int qi)
{
  if(!c) c=++tsz;
  sum[c]++;
  if(ss==se) return;
  int mid=ss+se>>1;
  if(qi<=mid) Set(ls[c],ss,mid,qi);
  else Set(rs[c],mid+1,se,qi);
}
int Get(int c, int ss, int se, int qs, int qe)
{
  if(qs>qe || qs>se || ss>qe) return 0;
  if(qs<=ss && qe>=se) return sum[c];
  int mid=ss+se>>1;
  return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int main()
{
  int n,q;
  scanf("%i %i",&n,&q);
  for(int i=1;i<=n;i++) scanf("%i %i",&a[i],&b[i]),uid[i]=i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

matryoshka.cpp: In function 'void Set(int&, int, int, int)':
matryoshka.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
matryoshka.cpp: In function 'int Get(int, int, int, int, int)':
matryoshka.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
matryoshka.cpp: In function 'int main()':
matryoshka.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
matryoshka.cpp:30:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&a[i],&b[i]),uid[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
matryoshka.cpp:31:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&x[i],&y[i]),qid[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49