Submission #897707

#TimeUsernameProblemLanguageResultExecution timeMemory
897707lovrotConstruction of Highway (JOI18_construction)C++17
16 / 100
278 ms856 KiB
#include <cstdio> #include <vector> #include <algorithm> #define EB emplace_back using namespace std; typedef long long ll; const int LOG = 12; const int N = 1 << LOG; int n, C[N]; int F[N]; void add(int x, int val) { for(++x; x < N; x += x & -x) F[x] += val; } int sum(int x) { int sum = 0; for(++x; x; x -= x & -x) sum += F[x]; return sum; } int P[N]; vector<int> S; int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", C + i); S.EB(C[i]); } sort(S.begin(), S.end()); S.erase(unique(S.begin(), S.end()), S.end()); for(int i = 0; i < n - 1; ++i) { int a, b; scanf("%d%d", &a, &b); ll cost = 0; for(int _a = a; _a; _a = P[_a]) { int pos = lower_bound(S.begin(), S.end(), C[_a]) - S.begin() + 1; cost += (ll) sum(pos - 1); add(pos, 1); } printf("%lld\n", cost); for(int _a = a; _a; _a = P[_a]) { int pos = lower_bound(S.begin(), S.end(), C[_a]) - S.begin() + 1; add(pos, -1); C[_a] = C[b]; } P[b] = a; } return 0; }

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
construction.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", C + i);
      |   ~~~~~^~~~~~~~~~~~~
construction.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...