제출 #623505

#제출 시각아이디문제언어결과실행 시간메모리
623505BalintR팀들 (IOI15_teams)C++17
100 / 100
1544 ms126820 KiB
#include <bits/stdc++.h> using namespace std; #include "teams.h" typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; #define pb push_back #define fs first #define sn second const int MN = 5e5 + 5, TREE_SZ = 1 << 20; int n, q; pii arr[MN]; int mem[10 << 20], tree[TREE_SZ], vecSz[TREE_SZ], sumDec[TREE_SZ], lastRem[TREE_SZ]; vi needReset; int t, l, v; const int r = TREE_SZ >> 1; void update(int i, int segL, int segR, int prvLast){ if(r <= segL || l >= segR || v == 0) return; needReset.pb(i); if(prvLast > lastRem[i]) sumDec[i] = 0; lastRem[i] = prvLast = max(lastRem[i], prvLast); if(l <= segL){ int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i]; if(gv <= v){ sumDec[i] = 0; lastRem[i] = t; v -= gv; return; } } if(segL + 1 == segR){ sumDec[i] += v; v = 0; return; } int mid = (segL + segR) >> 1; int oldV = v; update(i * 2, segL, mid, prvLast); sumDec[i] += oldV - v; if(v == 0) return; oldV = v; update(i * 2 + 1, mid, segR, prvLast); sumDec[i] += oldV - v; } void init(int N, int *A, int *B){ n = N; for (int i = 0; i < n; ++i) { arr[i] = {A[i], B[i]}; for(int j = r + B[i]; j; j >>= 1) vecSz[j]++; } sort(arr, arr + n); for (int i = 1; i < TREE_SZ; ++i) { tree[i] = tree[i-1] + vecSz[i-1]; vecSz[i-1] = 0; } for (int i = 0; i < n; ++i) { for(int j = r + arr[i].sn; j; j >>= 1){ mem[tree[j] + vecSz[j]++] = arr[i].fs; } } } int can(int k, int *reqSizes){ ll sum = 0; for (int i = 0; i < k; ++i) sum += reqSizes[i]; if(sum > n) return 0; sort(reqSizes, reqSizes + k); bool works = true; for (int i = 0; i < k; ++i) { t = l = v = reqSizes[i]; update(1, 0, r, 0); if(v){ works = false; break; } } for(int ind : needReset) sumDec[ind] = lastRem[ind] = 0; needReset.clear(); return works; }

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

teams.cpp: In function 'void update(int, int, int, int)':
teams.cpp:27:140: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   27 |         int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i];
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...