Submission #224252

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
224252	2020-04-17 15:16:00	jamielim	Klasika (COCI20_klasika)	C++14	33 / 110	2907 ms	441540 KiB

klasika

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 mp make_pair
const int MAXN=200005;
const int BITS=30;
int n=1,q,ctr=1;
pair<int,pair<int,int> > query[MAXN];
vector<pair<int,int> > adj[MAXN];
int l[MAXN],r[MAXN],x[MAXN]; //discovery, finish, xor from root
struct trie{
  set<int> s;
  trie *z,*o;
  trie(){z=o=NULL;}
  void add(int h,int v,int idx){ //h: height, number of bits; v: value at subtree root; idx: discovery index being added
    s.insert(idx);
    if(h<0)return;
    if(v&(1<<h)){
      if(o==NULL)o=new trie();
      o->add(h-1,v,idx);
    }else{
      if(z==NULL)z=new trie();
      z->add(h-1,v,idx);
    }
  }
  int get(int h,int v,int fr,int to){ //h: height, number of bits; v: value of query node; [fr,to): range allowed
    if(h<0)return 0;
    if((v&(1<<h))==0){ //want 1
      if(o==NULL||o->s.lower_bound(fr)==o->s.upper_bound(to))return z->get(h-1,v,fr,to);
      return (1<<h)+o->get(h-1,v,fr,to);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
klasika.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d",op,&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 33 / 33
• Subtask 4: 0 / 44