oj.uz

답안 #897605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897605 2024-01-03T13:22:34 Z coding_monk3 Examination (JOI19_examination) C++17
100 / 100
 2922 ms 43516 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 = 500;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1884 KB Output is correct
9 Correct 8 ms 2088 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1624 KB Output is correct
12 Correct 4 ms 1112 KB Output is correct
13 Correct 8 ms 1884 KB Output is correct
14 Correct 8 ms 2080 KB Output is correct
15 Correct 8 ms 1884 KB Output is correct
16 Correct 6 ms 1404 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

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 30532 KB Output is correct
2 Correct 495 ms 30508 KB Output is correct
3 Correct 542 ms 30440 KB Output is correct
4 Correct 1593 ms 21100 KB Output is correct
5 Correct 1664 ms 21084 KB Output is correct
6 Correct 127 ms 11868 KB Output is correct
7 Correct 318 ms 30516 KB Output is correct
8 Correct 331 ms 30528 KB Output is correct
9 Correct 276 ms 30472 KB Output is correct
10 Correct 581 ms 20780 KB Output is correct
11 Correct 560 ms 20900 KB Output is correct
12 Correct 104 ms 11308 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 30532 KB Output is correct
2 Correct 495 ms 30508 KB Output is correct
3 Correct 542 ms 30440 KB Output is correct
4 Correct 1593 ms 21100 KB Output is correct
5 Correct 1664 ms 21084 KB Output is correct
6 Correct 127 ms 11868 KB Output is correct
7 Correct 318 ms 30516 KB Output is correct
8 Correct 331 ms 30528 KB Output is correct
9 Correct 276 ms 30472 KB Output is correct
10 Correct 581 ms 20780 KB Output is correct
11 Correct 560 ms 20900 KB Output is correct
12 Correct 104 ms 11308 KB Output is correct
13 Correct 500 ms 30448 KB Output is correct
14 Correct 554 ms 30504 KB Output is correct
15 Correct 502 ms 30628 KB Output is correct
16 Correct 1612 ms 21172 KB Output is correct
17 Correct 1631 ms 21116 KB Output is correct
18 Correct 136 ms 11784 KB Output is correct
19 Correct 500 ms 30504 KB Output is correct
20 Correct 502 ms 30540 KB Output is correct
21 Correct 394 ms 30332 KB Output is correct
22 Correct 566 ms 20784 KB Output is correct
23 Correct 538 ms 20736 KB Output is correct
24 Correct 97 ms 11144 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1884 KB Output is correct
9 Correct 8 ms 2088 KB Output is correct
10 Correct 8 ms 1628 KB Output is correct
11 Correct 8 ms 1624 KB Output is correct
12 Correct 4 ms 1112 KB Output is correct
13 Correct 8 ms 1884 KB Output is correct
14 Correct 8 ms 2080 KB Output is correct
15 Correct 8 ms 1884 KB Output is correct
16 Correct 6 ms 1404 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 507 ms 30532 KB Output is correct
20 Correct 495 ms 30508 KB Output is correct
21 Correct 542 ms 30440 KB Output is correct
22 Correct 1593 ms 21100 KB Output is correct
23 Correct 1664 ms 21084 KB Output is correct
24 Correct 127 ms 11868 KB Output is correct
25 Correct 318 ms 30516 KB Output is correct
26 Correct 331 ms 30528 KB Output is correct
27 Correct 276 ms 30472 KB Output is correct
28 Correct 581 ms 20780 KB Output is correct
29 Correct 560 ms 20900 KB Output is correct
30 Correct 104 ms 11308 KB Output is correct
31 Correct 500 ms 30448 KB Output is correct
32 Correct 554 ms 30504 KB Output is correct
33 Correct 502 ms 30628 KB Output is correct
34 Correct 1612 ms 21172 KB Output is correct
35 Correct 1631 ms 21116 KB Output is correct
36 Correct 136 ms 11784 KB Output is correct
37 Correct 500 ms 30504 KB Output is correct
38 Correct 502 ms 30540 KB Output is correct
39 Correct 394 ms 30332 KB Output is correct
40 Correct 566 ms 20784 KB Output is correct
41 Correct 538 ms 20736 KB Output is correct
42 Correct 97 ms 11144 KB Output is correct
43 Correct 577 ms 43148 KB Output is correct
44 Correct 564 ms 43180 KB Output is correct
45 Correct 563 ms 43000 KB Output is correct
46 Correct 2861 ms 27208 KB Output is correct
47 Correct 2922 ms 27228 KB Output is correct
48 Correct 124 ms 11664 KB Output is correct
49 Correct 394 ms 43004 KB Output is correct
50 Correct 387 ms 43516 KB Output is correct
51 Correct 313 ms 43004 KB Output is correct
52 Correct 576 ms 26916 KB Output is correct
53 Correct 587 ms 26940 KB Output is correct