Submission #448196

#TimeUsernameProblemLanguageResultExecution timeMemory
448196spatarelFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
2 ms1868 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxK = 200'000; const int logN = 20; const long long INF = 1'000'000'000'000'000'000LL; int N, K; vector<long long> T(1+maxK); struct segtree { int l; int r; vector<long long> v; segtree* left = NULL; segtree* right = NULL; segtree() { ; } ~segtree() { if (left != NULL) delete left; if (right != NULL) delete right; } segtree(int L, int R) { l = L; r = R; if(l == r) { v.push_back(T[l]); } else { int m = (l+r)/2; this->left = new segtree(l, m); this->right = new segtree(m+1, r); for(int x: left->v) v.push_back(x); for(int y: right->v) v.push_back(y); sort(v.begin(), v.end()); } } int query(int L, int R, long long X, long long Y) { // cerr << l << ' ' << r << " query " << L << ' ' << R << ' ' << X << ' ' << Y << '\n'; if(X > Y) return 0; L = max(L, l); R = min(R, r); if(L > R) return 0; if(R < l || r < L) return 0; else if(L <= l && r <= R) { // cerr << "check A\n"; int lo = -1; for(int bit = logN; bit >= 0; bit--) { if(lo + (1 << bit) >= v.size()) continue; if(v[lo + (1 << bit)] >= X) continue; lo += (1 << bit); } // cerr << "check B\n"; lo++; if(lo >= v.size() || v[lo] < X || Y < v[lo]) return 0; // cerr << "check C\n"; int hi = -1; for(int bit = logN; bit >= 0; bit--) { if(hi + (1 << bit) >= v.size()) continue; if(v[hi + (1 << bit)] > Y) continue; hi += (1 << bit); } if(hi == -1 || hi >= v.size() || v[hi] < X || Y < v[hi] || hi < lo) return 0; // cerr << "check D\n"; // cerr << l << ' ' << r << " query " << L << ' ' << R << ' ' << X << ' ' << Y << " done \n"; return hi-lo+1; } else return left->query(L, R, X, Y) + right->query(L, R, X, Y); } int get_last(long long A, long long B) { // cerr << l << ' ' << r << " get last " << A << ' ' << B << '\n'; if(l == r) return l; else if(right->query(1, N, A, B) >= 1) return right->get_last(A, B); else return left->get_last(A, B); // cerr << l << ' ' << r << " get last " << A << ' ' << B << " done\n"; } }; int main() { cin >> N >> K; long long A[N+1], B[N+1]; for(int i = 1; i <= N; i++) cin >> A[i] >> B[i]; for(int j = 1; j <= K; j++) cin >> T[j]; T[0] = -1; segtree S(0, N); long long res = 0; // cerr << "check\n"; for(int i = 1; i <= N; i++) { // cerr << "i = " << i << '\n'; if(A[i] == B[i]) { res += A[i]; continue; } int last_pos = S.get_last(min(A[i], B[i]), max(A[i], B[i]) - 1); // cerr << i << ' ' << "A \n"; if(last_pos == 0) { // cerr << i << ' ' << "B1 \n"; int Q = S.query(1, N, max(A[i], B[i]), INF); if(Q % 2 == 0) res += A[i]; else res += B[i]; // cerr << i << ' ' << "B1 - done \n"; } else { // cerr << i << ' ' << "B2 \n"; int Q = S.query(last_pos + 1, N, max(A[i], B[i]), INF); if(Q % 2 == 0) res += max(A[i], B[i]); else res += min(A[i], B[i]); // cerr << i << ' ' << "B2 - done \n"; } } cout << res << '\n'; }

Compilation message (stderr)

fortune_telling2.cpp: In member function 'int segtree::query(int, int, long long int, long long int)':
fortune_telling2.cpp:69:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 if(lo + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
fortune_telling2.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if(lo >= v.size() || v[lo] < X || Y < v[lo]) return 0;
      |                ~~~^~~~~~~~~~~
fortune_telling2.cpp:82:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if(hi + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
fortune_telling2.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             if(hi == -1 || hi >= v.size() || v[hi] < X || Y < v[hi] || hi < lo) return 0;
      |                            ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...