oj.uz

답안 #846932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846932 2023-09-08T16:58:44 Z HoriaHaivas RMQ (NOI17_rmq) C++14
0 / 100
 1 ms 6492 KB 
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct qq
{
    int l;
    int r;
    int x;
};

struct ptval
{
    int nr;
    int poz;
};

ptval val[100001];
const int inf=INT_MAX;
qq query[100001];
qq query2[100001];
qq aux[100001];
int st[100001];
int finl[100001];
bool placed[100001];
bool used[100001];
int lazy[400001];

bool cmp (qq a, qq b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    else if (a.l!=b.l)
        return a.l<b.l;
    else
        return a.r<b.r;
}

bool cmp2(ptval a, ptval b)
{
    return a.nr>b.nr;
}

bool cmp3 (qq a, qq b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    else if (a.l!=b.l)
        return a.l<b.l;
    else
        return a.r<b.r;
}

void propagate(int parent, int child)
{
    lazy[child]=lazy[parent];
}

void lazy_update (int l, int r, int val, int qa, int qb, int x)
{
    if (lazy[val]!=-1)
    {
        if (r!=l)
        {
            propagate(val,val*2);
            propagate(val,val*2+1);
        }
        lazy[val]=-1;
    }
    if (l>qb || r<qa)
        return;
    if (qa<=l && r<=qb)
    {
        lazy[val]=x;
        return;
    }
    int mid;
    mid=(l+r)/2;
    if (qa<=mid)
        lazy_update(l,mid,val*2,qa,qb,x);
    if (qb>mid)
        lazy_update(mid+1,r,val*2+1,qa,qb,x);
}

int qry (int l, int r, int val, int qa, int qb)
{
    if (qa<=l && r<=qb)
    {
        return lazy[val];
    }
    if (lazy[val]!=-1)
    {
        if (r!=l)
        {
            propagate(val,val*2);
            propagate(val,val*2+1);
        }
        lazy[val]=-1;
    }
    if (r<qa || l>qb)
        return inf;
    int mid,ans;
    mid=(l+r)/2;
    ans=inf;
    if (qa<=mid)
        ans=min(ans,qry(l,mid,val*2,qa,qb));
    if (qb>mid)
        ans=min(ans,qry(mid+1,r,val*2+1,qa,qb));
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n,q,i,j,t,q2,big,dif,k;
    bool ok;
    ok=true;
    cin >> n >> q;
    for (i=1; i<=q; i++)
    {
        cin >> query[i].l >> query[i].r >> query[i].x;
        query2[i]=query[i];
    }
    sort(query+1,query+1+q,cmp);
    sort(query2+1,query2+1+q,cmp);
    for (j=1;j<=n;j++)
    {
         finl[j]=-1;
    }
    for (j=1; j<=q; j++)
    {
         for (k=query[j].l+1;k<=query[j].r+1;k++)
         {
              finl[k]=query[j].x;
         }
    }
    for (j=1;j<=n;j++)
    {
         if (finl[j]!=-1)
         cout << finl[j] << " ";
         else
         cout << n-1 << " ";
    }
    return 0;
}

Compilation message

rmq.cpp: In function 'int main()':
rmq.cpp:124:17: warning: unused variable 't' [-Wunused-variable]
  124 |     int n,q,i,j,t,q2,big,dif,k;
      |                 ^
rmq.cpp:124:19: warning: unused variable 'q2' [-Wunused-variable]
  124 |     int n,q,i,j,t,q2,big,dif,k;
      |                   ^~
rmq.cpp:124:22: warning: unused variable 'big' [-Wunused-variable]
  124 |     int n,q,i,j,t,q2,big,dif,k;
      |                      ^~~
rmq.cpp:124:26: warning: unused variable 'dif' [-Wunused-variable]
  124 |     int n,q,i,j,t,q2,big,dif,k;
      |                          ^~~
rmq.cpp:125:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  125 |     bool ok;
      |          ^~

Subtask #1
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 6492 KB Output is partially correct
2 Partially correct 1 ms 6492 KB Output is partially correct
3 Partially correct 1 ms 6492 KB Output is partially correct
4 Partially correct 1 ms 6492 KB Output is partially correct
5 Partially correct 1 ms 6492 KB Output is partially correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 6492 KB Output is partially correct
2 Partially correct 1 ms 6492 KB Output is partially correct
3 Partially correct 1 ms 6492 KB Output is partially correct
4 Partially correct 1 ms 6492 KB Output is partially correct
5 Partially correct 1 ms 6492 KB Output is partially correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 6492 KB Output is partially correct
2 Partially correct 1 ms 6492 KB Output is partially correct
3 Partially correct 1 ms 6492 KB Output is partially correct
4 Partially correct 1 ms 6492 KB Output is partially correct
5 Partially correct 1 ms 6492 KB Output is partially correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -