제출 #375291

#제출 시각아이디문제언어결과실행 시간메모리
375291hhh07새로운 문제 (POI11_met)C++14
100 / 100
3106 ms43456 KiB
#include <iostream> #include <algorithm> #include <cmath> #include <map> #include <climits> #include <vector> #include <utility> using namespace std; typedef unsigned long long ll; typedef pair<ll, ll> ii; vector<ll> fen(3e5 + 3, 0); ll n, m; ll sum(ll k){ ll s = 0; while(k > 0){ s += fen[k]; k -= k&-k; } return s; } void add(ll k, ll x){ while(k <= m + 2){ fen[k] += x; k += k&-k; } } struct query{ ll l, r, val; }; int main(){ cin >> n >> m; ll p[n]; int o; vector<vector<ll>> states(n + 1, vector<ll> ()); for (ll i = 0; i < m; i++){ cin >> o; states[o - 1].push_back(i); } for (ll i = 0; i < n; i++) cin >> p[i]; ll k; cin >> k; vector<query> q; query Q; for (ll i = 0; i < k; i++){ cin >> Q.l >> Q.r >> Q.val; Q.l--; Q.r--; q.push_back(Q); } vector<ll> lo(n, 0), hi(n, k), rj(n, -1); ll cnt = 0; while(cnt < n){ vector<ii> mid(n); for (ll i = 0; i < n; i++) mid[i] = {(lo[i] + hi[i])/2, i}; sort(mid.begin(), mid.end()); for (int i = 0; i <= m + 2; i++) fen[i] = 0; ll j = 0; for (ll i = 0; i < k; i++){ if (q[i].l <= q[i].r){ add(q[i].l + 1, q[i].val); add(q[i].r + 2, -q[i].val); } else{ add(q[i].l + 1, q[i].val); add(m + 1, -q[i].val); add(1, q[i].val); add(q[i].r + 2, -q[i].val); } while(j < n && mid[j].first == i){ ll idx = mid[j].second; if (rj[idx] == -1){ ll suma = 0; for (ll l = 0; l < states[idx].size(); l++){ suma += sum(states[idx][l] + 1); if (suma >= p[idx]) break; } if (suma >= p[idx]) hi[idx] = i; else lo[idx] = i + 1; if (lo[idx] >= hi[idx]){ cnt++; rj[idx] = lo[idx]; } } j++; } } } for (ll i = 0; i < n; i++){ if (rj[i] == k) cout << "NIE" << endl; else cout << rj[i] + 1 << endl; } return 0; }

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

met.cpp: In function 'int main()':
met.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i <= m + 2; i++)
      |                         ~~^~~~~~~~
met.cpp:81:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long unsigned int>, long long unsigned int>::value_type' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   81 |                 if (rj[idx] == -1){
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...