Submission #244917

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
244917	2020-07-05 09:23:59	Red_Inside	Fireworks (APIO16_fireworks)	C++17	100 / 100	230 ms	50332 KiB

fireworks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * Author: Seokhwan Choi
 * Time Complexity: O((N+M) (log (N+M))^2 )
 */
#include<stdio.h>
#include<queue>
#define MAXN 300100
int n,m;
int p[MAXN];
int c[MAXN];
struct ndata{//contains data for subtree (y=f(x), where y is minimum cost when distance to all leaf node is x
  long long int a,b;//y=ax+b at large x
  std::priority_queue<long long int> *pq;//saves slope changing points, slope change by 1 at each element
  ndata operator+(ndata r){//merge two data by adding them
    ndata s;//result(merged data)
    s.a=a+r.a;
    s.b=b+r.b;
    if(pq->size()>r.pq->size()){//merge smaller priority queue to larger priority queue
      s.pq=pq;
      while(r.pq->size()!=0){
        s.pq->push(r.pq->top());
        r.pq->pop();
      }
    }
    else{
      s.pq=r.pq;
      while(pq->size()!=0){
        s.pq->push(pq->top());
        pq->pop();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i],&c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45