oj.uz

Submission #897602

# Submission time Handle Problem Language Result Execution time Memory
897602 2024-01-03T13:20:26 Z coding_monk3 Examination (JOI19_examination) C++17
100 / 100
 2611 ms 48464 KB 
#include <bits/stdc++.h>
using namespace std;

// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x)	scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x)	scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s)	cin >> s
#define pi(x)	printf("%d\n",x)
#define pi2(x,y)	printf("%d %d\n",x,y)
#define pl(x)	printf("%lld\n",x)
#define pl2(x,y)	printf("%lld %lld\n",x,y)
#define ps(s)	cout << s << endl
#define py	    printf("YES\n")
#define pn	    printf("NO\n")
#define pnl	    printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})

#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))

// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)

// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;

// Containers
typedef pair<int, int>	    pii;
typedef pair<ll, ll>	    pll;
typedef vector<int>		    vi;
typedef vector<ll>		    vl;
typedef vector<pii>		    vpii;
typedef vector<pll>		    vpll;
typedef vector<vi>		    vvi;
typedef vector<vl>		    vvl;
typedef pair<string,string> pss;
typedef map<int, int>	    mii;

// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a)  vi a(n); rep(i,n) si(a[i]) 
#define takearri1(n,a)  vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a)  vl a(n); rep(i,n) sl(a[i]) 
#define takearrl1(n,a)  vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i]) 

// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);

template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);

template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);

template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}

template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}

template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = ";  _print(x); cerr << endl;
#else
#define deb(x)
#endif


inline string inttostr(ll a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline ll strtoint(string a){
  char x[100]; ll res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string getstr(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = sz(s); 
  rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}
 
inline string lowercase(string s){
  int n = sz(s); 
  rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

const int LOGN = 30;
const int MAXN = 1 << LOGN;

ll hilbertorder(int x, int y)
{
	ll d = 0;
	for (int s = 1 << (LOGN - 1); s; s >>= 1)
	{
		bool rx = x & s, ry = y & s;
		d = d << 2 | ((rx * 3) ^ static_cast<int>(ry));
		if (!ry)
		{
			if (rx)
			{
				x = MAXN - x;
				y = MAXN - y;
			}
			swap(x, y);
		}
	}
	return d;
}

bool cmp(vl &a, vl &b)
{
  return a[4] < b[4];
}

int f[100000 + 5];
const int B_SIZE = 300;
const int block_ct = 100000/B_SIZE + 5;
int block[block_ct];
vi d;

void add(vpii &v, int lb)
{
    for (int i = sz(v) - 1; i >= 0; i--)
    {
        if(v[i].ff < lb) return;
        int x = v[i].ss;
        f[x]++;
        block[x/B_SIZE]++;
    }
}

void remove(vpii &v, int lb)
{
    for (int i = sz(v) - 1; i >= 0; i--)
    {
        if(v[i].ff < lb) return;
        int x = v[i].ss;
        f[x]--;
        block[x/B_SIZE]--;
    }
}

int get(int k)
{
    int ans = 0;
    int curB = k/B_SIZE;
    loop(i,k,(curB+1)*B_SIZE) ans += f[i];
    loop(i,curB+1,block_ct) ans += block[i];

    return ans;
}

int main()
{
  clr(f); clr(block);
  takei2(n,q); 
  d.resize(n);
  map<int,vi> m1,m2;
  rep(i,n) 
  {
    takei2(s,t);
    m1[s].pb(t);
    m2[t].pb(s);
    d[i] = s+t;
  }
  // Coordinate Compression 
  sortv(d);
  d.resize(unique(all(d)) - d.begin());
  

  vector<vpii> left; vi li;
  for(auto &pr : m1)
  {
    vi &v = pr.ss;
    vpii tmp;
    sortv(v);
    for(auto ele : v)
    {
        tmp.pb({ele , lower_bound(all(d) , ele+pr.ff) - d.begin()});
    }
    left.pb(tmp);
    li.pb(pr.ff);
  }
  vector<vpii> right; vi ri;
  for(auto &pr : m2)
  {
    vi &v = pr.ss;
    vpii tmp;
    sortv(v);
    for(auto ele : v)
    {
        tmp.pb({ele , lower_bound(all(d) , ele+pr.ff) - d.begin()});
    }
    right.pb(tmp);
    ri.pb(pr.ff);
  }
  
  vvl queries(q,vl(5));
  rep(i,q)
  {
    takei2(l,r); takei(k);
    
    queries[i][0] = l;
    queries[i][1] = r;
    queries[i][2] = i;
    queries[i][3] = lower_bound(all(d) , k) - d.begin();
    queries[i][4] = hilbertorder(l,r);
  }
  sort(all(queries) , cmp);
  
  int pl = sz(li), pr = sz(ri);
  vi ans(q);
  rep(i,q)
  {
    int l = queries[i][0] , r = queries[i][1] , id = queries[i][2], k = queries[i][3];

    while(pl > 0 and li[pl-1] >= l) 
    {
        pl--;
        if(pr < sz(ri)) add(left[pl] , ri[pr]);
    }

    while(pr > 0 and ri[pr-1] >= r) 
    {
        pr--;
        if(pl < sz(li)) add(right[pr] , li[pl]);
    }

    while(pl < sz(li) and li[pl] < l) 
    {
        if(pr < sz(ri)) remove(left[pl] , ri[pr]);
        pl++;
    }
    
    while(pr < sz(ri) and ri[pr] < r) 
    {
        if(pl < sz(li)) remove(right[pr] , li[pl]);
        pr++;
    }
    
    ans[id] = get(k);
  }
  for(auto i : ans) pi(i);
  return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Compilation message

examination.cpp: In function 'std::string uppercase(std::string)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
examination.cpp:138:3: note: in expansion of macro 'rep'
  138 |   rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
examination.cpp: In function 'std::string lowercase(std::string)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
examination.cpp:144:3: note: in expansion of macro 'rep'
  144 |   rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
examination.cpp: In function 'int get(int)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:210:5: note: in expansion of macro 'loop'
  210 |     loop(i,k,(curB+1)*B_SIZE) ans += f[i];
      |     ^~~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:211:5: note: in expansion of macro 'loop'
  211 |     loop(i,curB+1,block_ct) ans += block[i];
      |     ^~~~
examination.cpp: In function 'int main()':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
examination.cpp:222:3: note: in expansion of macro 'rep'
  222 |   rep(i,n)
      |   ^~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
examination.cpp:262:3: note: in expansion of macro 'rep'
  262 |   rep(i,q)
      |   ^~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
examination.cpp:47:18: note: in expansion of macro 'loop'
   47 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
examination.cpp:276:3: note: in expansion of macro 'rep'
  276 |   rep(i,q)
      |   ^~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
examination.cpp:219:3: note: in expansion of macro 'takei2'
  219 |   takei2(n,q);
      |   ^~~~~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
examination.cpp:224:5: note: in expansion of macro 'takei2'
  224 |     takei2(s,t);
      |     ^~~~~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
   69 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
examination.cpp:264:5: note: in expansion of macro 'takei2'
  264 |     takei2(l,r); takei(k);
      |     ^~~~~~
examination.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
examination.cpp:68:25: note: in expansion of macro 'si'
   68 | #define takei(a) int a; si(a)
      |                         ^~
examination.cpp:264:18: note: in expansion of macro 'takei'
  264 |     takei2(l,r); takei(k);
      |                  ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 828 KB Output is correct
6 Correct 0 ms 836 KB Output is correct
7 Correct 9 ms 2384 KB Output is correct
8 Correct 8 ms 2240 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1624 KB Output is correct
12 Correct 5 ms 1112 KB Output is correct
13 Correct 8 ms 2128 KB Output is correct
14 Correct 8 ms 2140 KB Output is correct
15 Correct 8 ms 2188 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 33032 KB Output is correct
2 Correct 483 ms 32920 KB Output is correct
3 Correct 492 ms 33032 KB Output is correct
4 Correct 1507 ms 22796 KB Output is correct
5 Correct 1558 ms 22848 KB Output is correct
6 Correct 110 ms 12812 KB Output is correct
7 Correct 326 ms 32776 KB Output is correct
8 Correct 358 ms 33032 KB Output is correct
9 Correct 277 ms 32680 KB Output is correct
10 Correct 571 ms 22616 KB Output is correct
11 Correct 548 ms 22552 KB Output is correct
12 Correct 107 ms 12084 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 33032 KB Output is correct
2 Correct 483 ms 32920 KB Output is correct
3 Correct 492 ms 33032 KB Output is correct
4 Correct 1507 ms 22796 KB Output is correct
5 Correct 1558 ms 22848 KB Output is correct
6 Correct 110 ms 12812 KB Output is correct
7 Correct 326 ms 32776 KB Output is correct
8 Correct 358 ms 33032 KB Output is correct
9 Correct 277 ms 32680 KB Output is correct
10 Correct 571 ms 22616 KB Output is correct
11 Correct 548 ms 22552 KB Output is correct
12 Correct 107 ms 12084 KB Output is correct
13 Correct 522 ms 33288 KB Output is correct
14 Correct 501 ms 33392 KB Output is correct
15 Correct 506 ms 32876 KB Output is correct
16 Correct 1527 ms 23316 KB Output is correct
17 Correct 1525 ms 23240 KB Output is correct
18 Correct 110 ms 12808 KB Output is correct
19 Correct 478 ms 33244 KB Output is correct
20 Correct 487 ms 33444 KB Output is correct
21 Correct 384 ms 33436 KB Output is correct
22 Correct 569 ms 22444 KB Output is correct
23 Correct 532 ms 22576 KB Output is correct
24 Correct 96 ms 12084 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 828 KB Output is correct
6 Correct 0 ms 836 KB Output is correct
7 Correct 9 ms 2384 KB Output is correct
8 Correct 8 ms 2240 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1624 KB Output is correct
12 Correct 5 ms 1112 KB Output is correct
13 Correct 8 ms 2128 KB Output is correct
14 Correct 8 ms 2140 KB Output is correct
15 Correct 8 ms 2188 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 501 ms 33032 KB Output is correct
20 Correct 483 ms 32920 KB Output is correct
21 Correct 492 ms 33032 KB Output is correct
22 Correct 1507 ms 22796 KB Output is correct
23 Correct 1558 ms 22848 KB Output is correct
24 Correct 110 ms 12812 KB Output is correct
25 Correct 326 ms 32776 KB Output is correct
26 Correct 358 ms 33032 KB Output is correct
27 Correct 277 ms 32680 KB Output is correct
28 Correct 571 ms 22616 KB Output is correct
29 Correct 548 ms 22552 KB Output is correct
30 Correct 107 ms 12084 KB Output is correct
31 Correct 522 ms 33288 KB Output is correct
32 Correct 501 ms 33392 KB Output is correct
33 Correct 506 ms 32876 KB Output is correct
34 Correct 1527 ms 23316 KB Output is correct
35 Correct 1525 ms 23240 KB Output is correct
36 Correct 110 ms 12808 KB Output is correct
37 Correct 478 ms 33244 KB Output is correct
38 Correct 487 ms 33444 KB Output is correct
39 Correct 384 ms 33436 KB Output is correct
40 Correct 569 ms 22444 KB Output is correct
41 Correct 532 ms 22576 KB Output is correct
42 Correct 96 ms 12084 KB Output is correct
43 Correct 569 ms 47828 KB Output is correct
44 Correct 563 ms 48464 KB Output is correct
45 Correct 558 ms 48400 KB Output is correct
46 Correct 2611 ms 30516 KB Output is correct
47 Correct 2590 ms 30544 KB Output is correct
48 Correct 111 ms 12680 KB Output is correct
49 Correct 399 ms 47928 KB Output is correct
50 Correct 370 ms 47616 KB Output is correct
51 Correct 316 ms 47764 KB Output is correct
52 Correct 580 ms 30220 KB Output is correct
53 Correct 579 ms 29576 KB Output is correct