Submission #655929

#TimeUsernameProblemLanguageResultExecution timeMemory
655929Do_you_copyVudu (COCI15_vudu)C++17
42 / 140
488 ms25808 KiB
/* Procrastination is the art of keeping up with yesterday */ #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ld = long double; using pii = pair <int, int>; mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 2e6 + 1; //const int Mod = 1e9 + 7; //const int inf = int n, p; int a[maxN]; int pre[maxN]; vector <int> node; int bit[maxN]; void update(int x, int val){ for (; x <= node.size(); x += x & -x) bit[x] += val; } int get(int x){ int res = 0; for (; x; x -= x & -x) res += bit[x]; return res; } void Init(){ cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; cin >> p; for (int i = 1; i <= n; ++i){ a[i] -= p; pre[i] = pre[i - 1] + a[i]; node.pb(pre[i]); } int ans = 0; node.pb(0); sort(node.begin(), node.end()); node.resize(unique(node.begin(), node.end()) - node.begin()); update(upper_bound(node.begin(), node.end(), 0) - node.begin(), 1); for (int i = 1; i <= n; ++i){ auto k = upper_bound(node.begin(), node.end(), pre[i]) - node.begin(); ans += get(k); //cerr << k << " " << get(k) << " "; k = upper_bound(node.begin(), node.end(), pre[i]) - node.begin(); update(k, 1); //cerr << k << "\n"; } cout << ans; } #define debug #define taskname "test" signed main(){ faster if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } int tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000); timeout.close(); #ifndef debug cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n"; #endif // debug } }

Compilation message (stderr)

vudu.cpp: In function 'void update(int, int)':
vudu.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (; x <= node.size(); x += x & -x)
      |            ~~^~~~~~~~~~~~~~
vudu.cpp: In function 'int main()':
vudu.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
vudu.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...