제출 #774671

#제출 시각아이디문제언어결과실행 시간메모리
774671ngrace팀들 (IOI15_teams)C++14
21 / 100
1209 ms366968 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 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); } 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 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); for(int i=0; i<M; i++){ dp[i] = getRect(0, K[i], K[i]) - K[i]; for(int j=0; j<i; j++){ dp[i] = min(dp[i], dp[j] + getRect(K[j]+1, K[i], K[i]) - K[i]); } if(dp[i]<0) return 0; } return 1; }

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

teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:49: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]
   49 |  int ind1 = distance(points.begin(), lower_bound(points.begin(), points.end(), p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:50: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]
   50 |  int ind2 = distance(points.begin(), lower_bound(points.begin(), points.end(), p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:75: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]
   75 |    if(pq.size()<K[i]) return 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...