제출 #530594

#제출 시각아이디문제언어결과실행 시간메모리
530594ajpiano팀들 (IOI15_teams)C++17
100 / 100
1905 ms115312 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; typedef pair<int,int> pi; const int large = 5e5+5; vector<pi> bit[large]; //r, val void binit(){ for(int i = 0; i < large; i++) bit[i].push_back({-large,0}); } void add(int pos, int r){ for(; pos < large; pos += pos&-pos) bit[pos].push_back({r,bit[pos].back().s+1}); } int sum(int pos, int fr){ int ans = 0; for(; pos > 0; pos -= pos&-pos){ int l = 0, r = bit[pos].size(); while(r-l > 1){ int mid = (l+r)>>1; if(bit[pos][mid].f <= fr) l = mid; else r = mid; } ans += bit[pos][l].s; } return ans; } int sum(int l1, int l2, int r1, int r2){ //finds from (l1, l2], (r1, r2] return sum(l2,r2)-sum(l1,r2)-sum(l2,r1)+sum(l1, r1); } int valfnd(int node, int r1, int r2){ int x = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r2+1,-1)))->s; int y = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r1+1, -1)))->s; return x-y; } int binsearch(int l2, int r1, int r2, int val){ int x = valfnd(l2,r1,r2); if(x < val) return binsearch(l2-(l2&-l2), r1,r2,val-x); int dif = l2&-l2; for(dif >>= 1; dif > 0; dif >>= 1){ x -= valfnd(l2-dif, r1, r2); if(x < val){ val -= x; return binsearch(l2-dif, r1, r2, val); } } return l2; } int n; void init(int _n, int _a[], int _b[]){ //input stuff n = _n; //a = _a; b = _b; binit(); vector<pi> ranges(n); // r,l for(int i = 0; i < n; i++){ ranges[i] = {_b[i], _a[i]}; } sort(ranges.begin(), ranges.end()); //increasing r order for(auto &p: ranges){ add(p.s,p.f); } } int can(int m, int k[]){ //fix input vector<int> k2; vector<pair<pi, int>> hchange = {{{0,n+1},0}}; //{x,y}, add at place for(int i = 0; i < m; i++) k2.push_back(k[i]); sort(k2.begin(), k2.end(), greater<int>()); for(int i = 0; i < m; i++){ int rem = k2[i]; int rp = k2[i]; while(rem > 0 && !hchange.empty()){ //remove if protected region is no longer valid if(hchange.back().f.f > k2[i]){ hchange.pop_back(); continue; } //find value of current protected region int ctop = hchange.back().f.s-1, cleft = hchange.back().f.f, cadd = hchange.back().s; int x = sum(cleft-1, rp, k2[i]-1, ctop)+cadd; //Move on if current region has too little if(rem > x){ rem -= x; rp = cleft-1; hchange.pop_back(); continue; } //Current region has just enough int boval = sum(cleft, rp, k2[i]-1, ctop); if(rem > boval){ hchange.pop_back(); hchange.push_back({{cleft, k2[i]}, x-rem}); rem = 0; continue; } //binary search to find position int l = binsearch(rp, k2[i]-1, ctop, rem); x = sum(l-1, rp, k2[i]-1, ctop); hchange.push_back({{l,k2[i]}, x-rem}); rem = 0; continue; } if(rem > 0) return 0; } return 1; }

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

teams.cpp: In function 'int sum(int, int)':
teams.cpp:30:37: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   30 |         int l = 0, r = bit[pos].size();
      |                        ~~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...