Submission #501577

#TimeUsernameProblemLanguageResultExecution timeMemory
501577Nuraly_SerikbayMeteors (POI11_met)C++14
0 / 100
6093 ms56436 KiB
#include <bits/stdc++.h> #define endl "\n" #define mp make_pair #define pb push_back #define F first #define S second #define sz size() #define rep(i,k,n) for(int i = k ; i <= n ; ++i) #define per(i,k,n) for(int i = k ; i >= n ; --i) #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define all(x) x.begin(),x.end() #define fr(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout) #define toqta return 0 #define PERMUTE next_permutation #define no cout<<"No"<<endl; #define yes cout<<"Yes"<<endl; #define a() a + 1, a + n + 1 using namespace std; /* #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse,-fgcse-lm") #pragma GCC optimize("-ftree-pre,-ftree-vrp") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") */ typedef long long ll; typedef unsigned long long ull; typedef string S; typedef double D; typedef long double lld; const int N = 1e6 + 17; const int modd = 1e9 + 7; const ll INF = 1e18 - 19; const int P = 37; const ll NN = 1e7 + 17; const D eps = 1e-19; const double pi = 3.141592653589793238462643383279 ; struct edge { ll a, b, len; bool operator<(const edge& other) { return len < other.len; } }; bool sortbysec(const pair<int,int> &a, const pair<int,int> &b){ return (a.second < b.second); } void pre (ll a) { cout << fixed << setprecision(a); return; } ll n, m; ll a[N], q, sum[N]; vector <ll> v[N]; ll t[N], mod[N]; ll L[N], R[N], x[N]; void push (ll l, ll r, ll v) { if (mod[v] != 0 && v * 2 + 1 < N) { mod[v * 2] += mod[v]; mod[v * 2 + 1] += mod[v]; mod[v] = 0; } } void update (ll l, ll r, ll tl, ll tr, ll v, ll val) { if (l <= tl && tr <= r) { mod[v] += val; push(tl, tr, v); return; } if (tr < l || r < tl) return; ll mid = tl + tr >> 1; push (tl, tr, v); update (l, r, tl, mid, v * 2, val); update (l, r, mid + 1, tr, v * 2 + 1, val); mod[v] = mod[v * 2] + mod[v * 2 + 1]; return; } ll get (ll v, ll tl, ll tr, ll pos) { if (tl == tr) { return mod[v]; } push(tl, tr, v); int mid = tl + tr >> 1; if (pos <= mid) return get(v * 2, tl, mid, pos); else return get(v * 2 + 1, mid + 1, tr, pos); } ll check (ll len, ll pos) { ll ans = 0; for (int i = 1; i <= len; ++i) { if (L[i] > R[i]) { update(L[i], m, 1, m, 1, x[i]); update(1, R[i], 1, m, 1, x[i]); } else { update(L[i], R[i], 1, m, 1, x[i]); } } for (int i = 0; i < v[pos].size(); ++i) { ans += get(1, 1, m, v[pos][i]); } for (int j = 1; j <= m * 4; ++j) mod[j] = 0; return ans; } void Solution (/*Nuraly.Serikbay*/) { cin >> n >> m; for (int i = 1; i <= m; ++ i) { cin >> a[i]; v[a[i]].pb(i); } for (int i = 1; i <= n; ++ i) { cin >> sum[i]; } cin >> q; for (int i = 1; i <= q; ++ i) { cin >> L[i] >> R[i] >> x[i]; } for (int i = 1; i <= n; ++ i) { ll l = 1, r = q; while (r - l > 0) { ll mid = l + r >> 1; if (check(mid, i) >= sum[i]) { r = mid; } else { l = mid + 1; } } if (check(r, i) < sum[i]) cout << "NIE" << endl; else cout << r << endl; } return; } int main () { YOSIK(); ll T = 1; //cin >> T; while (T --) { Solution (); } exit (0); }/* */

Compilation message (stderr)

met.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
met.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  ll mid = tl + tr >> 1;
      |           ~~~^~~~
met.cpp: In function 'll get(ll, ll, ll, ll)':
met.cpp:103:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |   int mid = tl + tr >> 1;
      |             ~~~^~~~
met.cpp: In function 'll check(ll, ll)':
met.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (int i = 0; i < v[pos].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
met.cpp: In function 'void Solution()':
met.cpp:141:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |    ll mid = l + r >> 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...