Submission #977459

#TimeUsernameProblemLanguageResultExecution timeMemory
977459shoryu386Money (IZhO17_money)C++17
100 / 100
156 ms21728 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define MX 1000007 int fwt[MX+1]; #define lsb(x) (x&(-x)) void update(int x, int k){ x++; for (; x < MX; x += lsb(x)){ fwt[x] += k; } } int sum(int x){ x++; int res = 0; for (; x != 0; x -= lsb(x)){ res += fwt[x]; } return res; } int query(int a, int b){ if (b < a) return 0; return sum(b) - sum(a-1); } main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; //attempt greedy int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x]; bitset<1000007> taken; int ans = 0; for (int zzz = 0; zzz < n; zzz++){ if (taken[zzz]){ continue; } ans++; taken[zzz] = 1; vector<int> items; items.push_back(arr[zzz]); for (int y = zzz+1; y < n; y++){ if (items.back() <= arr[y] && query(arr[zzz]+1, arr[y]-1) == 0){ taken[y] = 1; items.push_back(arr[y]); } else{ break; } } for (auto y : items){ update(y, 1); } } cout << ans; }

Compilation message (stderr)

money.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){ ios_base::sync_with_stdio(0); cin.tie(0);
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...