oj.uz

Submission #375796

# Submission time Handle Problem Language Result Execution time Memory
375796 2021-03-10T02:30:03 Z daniel920712 Two Antennas (JOI19_antennas) C++14
24 / 100
 1824 ms 524292 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;
struct A
{

    int l,r;
    int nxl,nxr;
    pair < int , int > ans;
}Node[1000005];
int all[1000005],now=1;
int ans[1000005];
int l[1000005],r[1000005];
vector < pair < int , int > > query[1000005];
int x[1000005],y[1000005];
vector < pair < int , int > > in[1000005];
vector < pair < int , int > > out[1000005];
pair < int , int > operator+(pair < int , int > a,pair < int , int > b)
{
    return make_pair(max(a.first,b.first),min(a.second,b.second));
}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    if(l==r)
    {
        Node[here].ans=make_pair(0,2e9);
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
void cha(int where,pair < int , int > con,int here)
{
    if(where==Node[here].l&&where==Node[here].r)
    {
        Node[here].ans=con;
        return;
    }
    if(where<=(Node[here].l+Node[here].r)/2) cha(where,con,Node[here].nxl);
    else cha(where,con,Node[here].nxr);
    Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
pair < int , int > Find(int l,int r,int here)
{
    if(l==Node[here].l&&r==Node[here].r) return Node[here].ans;
    if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
    else return Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
}
pair < int , int > tt;
int main()
{
    int N,M,ok=0,i,j;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    {
        scanf("%d %d %d",&all[i],&l[i],&r[i]);
        if(i-l[i]>=1)
        {
            in[max(1,i-r[i])].push_back(make_pair(i,all[i]));
            out[i-l[i]+1].push_back(make_pair(i,all[i]));
        }
    }
    scanf("%d",&M);
    for(i=0;i<M;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        for(j=x[i];j<=y[i];j++) query[j].push_back(make_pair(y[i],i));
    }
    build(1,N,0);
    for(i=1;i<=N;i++)
    {
        for(auto j:in[i]) cha(j.first,make_pair(j.second,j.second),0);
        for(auto j:out[i]) cha(j.first,make_pair(0,2e9),0);
        for(auto j:query[i])
        {
            if(i+l[i]<=j.first)
            {
                tt=Find(i+l[i],min(j.first,i+r[i]),0);
                if(tt.first) ans[j.second]=max(ans[j.second],abs(all[i]-tt.first));
                if(tt.second!=2000000000) ans[j.second]=max(ans[j.second],abs(all[i]-tt.second));
            }
        }
    }
    for(i=0;i<M;i++)
    {
        if(ans[i]==0) printf("-1\n");
        else printf("%d\n",ans[i]);
    }

    return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:61:13: warning: unused variable 'ok' [-Wunused-variable]
   61 |     int N,M,ok=0,i,j;
      |             ^~
antennas.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
antennas.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d %d %d",&all[i],&l[i],&r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d",&M);
      |     ~~~~~^~~~~~~~~
antennas.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94316 KB Output is correct
2 Correct 57 ms 94572 KB Output is correct
3 Correct 57 ms 94700 KB Output is correct
4 Correct 56 ms 94572 KB Output is correct
5 Correct 64 ms 94444 KB Output is correct
6 Correct 55 ms 94444 KB Output is correct
7 Correct 67 ms 94720 KB Output is correct
8 Correct 66 ms 94572 KB Output is correct
9 Correct 55 ms 94444 KB Output is correct
10 Correct 63 ms 94580 KB Output is correct
11 Correct 57 ms 94444 KB Output is correct
12 Correct 63 ms 94576 KB Output is correct
13 Correct 57 ms 94444 KB Output is correct
14 Correct 58 ms 94572 KB Output is correct
15 Correct 59 ms 94572 KB Output is correct
16 Correct 56 ms 94572 KB Output is correct
17 Correct 60 ms 94572 KB Output is correct
18 Correct 55 ms 94608 KB Output is correct
19 Correct 56 ms 94316 KB Output is correct
20 Correct 54 ms 94572 KB Output is correct
21 Correct 58 ms 94588 KB Output is correct
22 Correct 71 ms 94572 KB Output is correct
23 Correct 55 ms 94572 KB Output is correct
24 Correct 56 ms 94504 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94316 KB Output is correct
2 Correct 57 ms 94572 KB Output is correct
3 Correct 57 ms 94700 KB Output is correct
4 Correct 56 ms 94572 KB Output is correct
5 Correct 64 ms 94444 KB Output is correct
6 Correct 55 ms 94444 KB Output is correct
7 Correct 67 ms 94720 KB Output is correct
8 Correct 66 ms 94572 KB Output is correct
9 Correct 55 ms 94444 KB Output is correct
10 Correct 63 ms 94580 KB Output is correct
11 Correct 57 ms 94444 KB Output is correct
12 Correct 63 ms 94576 KB Output is correct
13 Correct 57 ms 94444 KB Output is correct
14 Correct 58 ms 94572 KB Output is correct
15 Correct 59 ms 94572 KB Output is correct
16 Correct 56 ms 94572 KB Output is correct
17 Correct 60 ms 94572 KB Output is correct
18 Correct 55 ms 94608 KB Output is correct
19 Correct 56 ms 94316 KB Output is correct
20 Correct 54 ms 94572 KB Output is correct
21 Correct 58 ms 94588 KB Output is correct
22 Correct 71 ms 94572 KB Output is correct
23 Correct 55 ms 94572 KB Output is correct
24 Correct 56 ms 94504 KB Output is correct
25 Correct 1824 ms 371528 KB Output is correct
26 Correct 477 ms 176284 KB Output is correct
27 Runtime error 1194 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 105976 KB Output is correct
2 Correct 341 ms 106968 KB Output is correct
3 Correct 238 ms 103144 KB Output is correct
4 Correct 344 ms 107108 KB Output is correct
5 Correct 164 ms 100072 KB Output is correct
6 Correct 329 ms 106980 KB Output is correct
7 Correct 270 ms 105316 KB Output is correct
8 Correct 335 ms 106980 KB Output is correct
9 Correct 86 ms 96236 KB Output is correct
10 Correct 332 ms 106980 KB Output is correct
11 Correct 214 ms 102252 KB Output is correct
12 Correct 316 ms 106980 KB Output is correct
13 Correct 227 ms 106724 KB Output is correct
14 Correct 216 ms 106212 KB Output is correct
15 Correct 198 ms 104988 KB Output is correct
16 Correct 207 ms 104992 KB Output is correct
17 Correct 230 ms 107108 KB Output is correct
18 Correct 212 ms 105572 KB Output is correct
19 Correct 215 ms 105832 KB Output is correct
20 Correct 214 ms 105960 KB Output is correct
21 Correct 218 ms 106724 KB Output is correct
22 Correct 217 ms 105956 KB Output is correct
23 Correct 218 ms 106084 KB Output is correct
24 Correct 200 ms 105016 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94316 KB Output is correct
2 Correct 57 ms 94572 KB Output is correct
3 Correct 57 ms 94700 KB Output is correct
4 Correct 56 ms 94572 KB Output is correct
5 Correct 64 ms 94444 KB Output is correct
6 Correct 55 ms 94444 KB Output is correct
7 Correct 67 ms 94720 KB Output is correct
8 Correct 66 ms 94572 KB Output is correct
9 Correct 55 ms 94444 KB Output is correct
10 Correct 63 ms 94580 KB Output is correct
11 Correct 57 ms 94444 KB Output is correct
12 Correct 63 ms 94576 KB Output is correct
13 Correct 57 ms 94444 KB Output is correct
14 Correct 58 ms 94572 KB Output is correct
15 Correct 59 ms 94572 KB Output is correct
16 Correct 56 ms 94572 KB Output is correct
17 Correct 60 ms 94572 KB Output is correct
18 Correct 55 ms 94608 KB Output is correct
19 Correct 56 ms 94316 KB Output is correct
20 Correct 54 ms 94572 KB Output is correct
21 Correct 58 ms 94588 KB Output is correct
22 Correct 71 ms 94572 KB Output is correct
23 Correct 55 ms 94572 KB Output is correct
24 Correct 56 ms 94504 KB Output is correct
25 Correct 1824 ms 371528 KB Output is correct
26 Correct 477 ms 176284 KB Output is correct
27 Runtime error 1194 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -