제출 #897611

#제출 시각아이디문제언어결과실행 시간메모리
897611coding_monk3Examination (JOI19_examination)C++17
100 / 100
2758 ms46180 KiB
#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; } // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

컴파일 시 표준 에러 (stderr) 메시지

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);
      |                  ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...