oj.uz

Submission #897611

# Submission time Handle Problem Language Result Execution time Memory
897611 2024-01-03T13:30:55 Z coding_monk3 Examination (JOI19_examination) C++17
100 / 100
 2758 ms 46180 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 = 350;
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 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 8 ms 2140 KB Output is correct
8 Correct 8 ms 2224 KB Output is correct
9 Correct 9 ms 2140 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1708 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 10 ms 2140 KB Output is correct
14 Correct 8 ms 2140 KB Output is correct
15 Correct 8 ms 2156 KB Output is correct
16 Correct 7 ms 1624 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 4 ms 1096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 32260 KB Output is correct
2 Correct 535 ms 32036 KB Output is correct
3 Correct 483 ms 32060 KB Output is correct
4 Correct 1544 ms 22120 KB Output is correct
5 Correct 1575 ms 22168 KB Output is correct
6 Correct 111 ms 12552 KB Output is correct
7 Correct 373 ms 32292 KB Output is correct
8 Correct 353 ms 32356 KB Output is correct
9 Correct 281 ms 31752 KB Output is correct
10 Correct 598 ms 21952 KB Output is correct
11 Correct 559 ms 21800 KB Output is correct
12 Correct 99 ms 11824 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 32260 KB Output is correct
2 Correct 535 ms 32036 KB Output is correct
3 Correct 483 ms 32060 KB Output is correct
4 Correct 1544 ms 22120 KB Output is correct
5 Correct 1575 ms 22168 KB Output is correct
6 Correct 111 ms 12552 KB Output is correct
7 Correct 373 ms 32292 KB Output is correct
8 Correct 353 ms 32356 KB Output is correct
9 Correct 281 ms 31752 KB Output is correct
10 Correct 598 ms 21952 KB Output is correct
11 Correct 559 ms 21800 KB Output is correct
12 Correct 99 ms 11824 KB Output is correct
13 Correct 500 ms 32440 KB Output is correct
14 Correct 497 ms 32252 KB Output is correct
15 Correct 518 ms 32032 KB Output is correct
16 Correct 1566 ms 22400 KB Output is correct
17 Correct 1588 ms 22384 KB Output is correct
18 Correct 116 ms 12452 KB Output is correct
19 Correct 507 ms 32264 KB Output is correct
20 Correct 516 ms 32328 KB Output is correct
21 Correct 393 ms 32308 KB Output is correct
22 Correct 564 ms 21916 KB Output is correct
23 Correct 555 ms 21784 KB Output is correct
24 Correct 103 ms 11828 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 8 ms 2140 KB Output is correct
8 Correct 8 ms 2224 KB Output is correct
9 Correct 9 ms 2140 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1708 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 10 ms 2140 KB Output is correct
14 Correct 8 ms 2140 KB Output is correct
15 Correct 8 ms 2156 KB Output is correct
16 Correct 7 ms 1624 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 4 ms 1096 KB Output is correct
19 Correct 497 ms 32260 KB Output is correct
20 Correct 535 ms 32036 KB Output is correct
21 Correct 483 ms 32060 KB Output is correct
22 Correct 1544 ms 22120 KB Output is correct
23 Correct 1575 ms 22168 KB Output is correct
24 Correct 111 ms 12552 KB Output is correct
25 Correct 373 ms 32292 KB Output is correct
26 Correct 353 ms 32356 KB Output is correct
27 Correct 281 ms 31752 KB Output is correct
28 Correct 598 ms 21952 KB Output is correct
29 Correct 559 ms 21800 KB Output is correct
30 Correct 99 ms 11824 KB Output is correct
31 Correct 500 ms 32440 KB Output is correct
32 Correct 497 ms 32252 KB Output is correct
33 Correct 518 ms 32032 KB Output is correct
34 Correct 1566 ms 22400 KB Output is correct
35 Correct 1588 ms 22384 KB Output is correct
36 Correct 116 ms 12452 KB Output is correct
37 Correct 507 ms 32264 KB Output is correct
38 Correct 516 ms 32328 KB Output is correct
39 Correct 393 ms 32308 KB Output is correct
40 Correct 564 ms 21916 KB Output is correct
41 Correct 555 ms 21784 KB Output is correct
42 Correct 103 ms 11828 KB Output is correct
43 Correct 613 ms 46044 KB Output is correct
44 Correct 581 ms 46180 KB Output is correct
45 Correct 578 ms 45924 KB Output is correct
46 Correct 2758 ms 29000 KB Output is correct
47 Correct 2697 ms 29028 KB Output is correct
48 Correct 121 ms 12220 KB Output is correct
49 Correct 377 ms 45568 KB Output is correct
50 Correct 379 ms 46080 KB Output is correct
51 Correct 361 ms 45400 KB Output is correct
52 Correct 582 ms 28636 KB Output is correct
53 Correct 589 ms 28460 KB Output is correct