제출 #774879

#제출 시각아이디문제언어결과실행 시간메모리
774879ngrace팀들 (IOI15_teams)C++14
77 / 100
4057 ms362336 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define v vector #define ii pair<int,int> #define fi first #define se second struct node{ node* l; node* r; int sum; node(int val){ l=nullptr; r=nullptr; sum=val; } node(node* lll, node* rr){ l=lll; r=rr; sum=l->sum + r->sum; } }; node* build(int l, int r){ if(l==r) return new node(0); int m=(l+r)/2; return new node(build(l,m), build(m+1,r)); } node* update(node* cur, int l, int r, int tar){ if(l==r) return new node(cur->sum+1); int m=(l+r)/2; if(tar<=m) return new node(update(cur->l, l, m, tar), cur->r); return new node(cur->l, update(cur->r, m+1, r, tar)); } int query(node* cur, int l, int r, int ql){ if(ql<=l) return cur->sum; int m=(l+r)/2, ret=0; if(ql<=m) ret += query(cur->l, l, m, ql); ret += query(cur->r, m+1, r, ql); return ret; } int binSearchQuery(node* curl, node* curr, int l, int r, int num){ //returns last place where num<amount holds if(l==r) return l; int m=(l+r)/2; int amount = curr->r->sum - curl->r->sum; if(num >= amount) return binSearchQuery(curl->l, curr->l, l,m, num - amount); return binSearchQuery(curl->r, curr->r, m+1, r, num); } int n; v<ii> points; v<node*> roots; int getRect(int x1, int x2, int y){ ii p1 = {x1, -1}, p2 = {x2+1, -1}; int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1)); int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2)); return query(roots[ind2], 1, n, y) - query(roots[ind1], 1, n, y); } int getSplit(int x1, int x2, int num){ ii p1 = {x1, -1}, p2 = {x2+1, -1}; int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1)); int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2)); return binSearchQuery(roots[ind1], roots[ind2], 1, n, num) + 1;//the first place where the suffix sum is >= num } void init(int N, int A[], int B[]) { n=N; for(int i=0; i<n; i++) points.push_back({A[i], B[i]}); roots.push_back(build(1,n)); sort(points.begin(), points.end()); for(ii it:points) roots.push_back(update(roots.back(), 1, n, it.se)); } int cnt=0; int can(int M, int K[]) { sort(K, K+M); if(M>400){ priority_queue<ii> pq; int j=0; for(int i=0; i<M; i++){ while(j<n && points[j].fi<=K[i]){ pq.push({-points[j].se, points[j].fi}); j++; } while(pq.size()>0 && -pq.top().fi<K[i]) pq.pop(); if(pq.size()<K[i]) return 0; for(int k=0; k<K[i]; k++) pq.pop(); } return 1; } v<int> dp(M); set<int> opt; priority_queue<pair<int,ii>> pq; for(int i=0; i<M; i++){ dp[i] = getRect(0, K[i], K[i]) - K[i]; int cnt=0; while(pq.size()>0 && pq.top().fi<=K[i]){ int j1=pq.top().se.fi; int j2=pq.top().se.se; pq.pop(); if(opt.find(j1)==opt.end() || opt.find(j2)==opt.end()) continue; opt.erase(j2); } if(opt.size()>0){ auto it=opt.end(); it--; int j=*it; dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]); } if(dp[i]<0) return 0; opt.insert(i); if(opt.size()>1){ auto it = opt.end(); it--; it--; int j1=*it; int j2=i; int k = (K[j1]==K[j2]) ? 0 : getSplit(K[j1]+1, K[j2], dp[j2]-dp[j1]); if(K[j1]==K[j2]) k= (dp[j2] - dp[j1] < 0) ? K[M-1]+1 : K[j2]+1; pq.push({k, {j1,j2}}); } } return 1; }

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

teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:57:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   57 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:58:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   58 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int getSplit(int, int, int)':
teams.cpp:63:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   63 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:64:21: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   64 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:90:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |    if(pq.size()<K[i]) return 0;
      |       ~~~~~~~~~^~~~~
teams.cpp:102:7: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
  102 |   int cnt=0;
      |       ^~~
teams.cpp:77:5: note: shadowed declaration is here
   77 | int cnt=0;
      |     ^~~
teams.cpp:102:7: warning: unused variable 'cnt' [-Wunused-variable]
  102 |   int cnt=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...