답안 #922094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922094 2024-02-05T02:39:42 Z astilate Meteors (POI11_met) C++14
0 / 100
794 ms 30904 KB
#include<bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define getint(n) int n; scanf("%d%*c", &n)
#define getll(n)  ll n; scanf("%lld%*c", &n)
#define inta int a; scanf("%d%*c", &a)
#define intab int a,b; scanf("%d%*c%d%*c", &a,&b)

#define forr(i, n) for(int i = 1; i <= (n); i++)
#define fors(i, s, e) for(int i = (s); i <= (e); i++)
#define fore(i, e, s) for(int i = (e); i >= (s); i--)

#define pb push_back
#define fi first
#define se second

#define prev _prev

using namespace std;

using ll = long long;
using pii = pair<int,int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vii=vector<pii>;

const int N = 3e5+7;
ll tree[N];
void update(int i, int x)
{
    while(i < N)
    {
        tree[i] += x;
        i += i&-i;
    }
}
void update(int l, int r, ll x)
{
    if(l < r)
    {
        update(l, x); 
        update(r+1, -x);
    }
    else
    {
        update(1, x); update(r+1, -x);
        update(l, x);
    }
}

ll query(int i)
{
    ll ret = 0;
    while(i) ret += tree[i], i-=i&-i;
    return ret;
}

vi arr[N]; vector<pair<pii, int> > q;
int ans[N]; int p[N];
void solve()
{
    getint(n); getint(m);
    forr(i, m)
    {
        getint(a);
        arr[a].pb(i);
    }
    forr(i, n) scanf("%d", p+i);
    getint(Q);
    forr(i, Q)
    {
        getint(l); getint(r); getint(a);
        q.pb({{l, r}, a});
    }
    
    vii now;
    int st = 20;
    while(st+1)
    {
        forr(i, n) if(ans[i]+(1<<st) <= Q) now.pb({ans[i]+(1<<st), i});
        st--;
        
        sort(all(now));
        
        auto it = now.begin();
        forr(i, Q)
        {
            auto [l, r] = q[i-1].fi;
            auto a = q[i-1].se;
            
            update(l, r, a);
            
            while(it != now.end() and it->fi == i)
            {
                ll x = 0;
                for(auto c : arr[it->se])
                    x += query(c);
                
                if(p[it->se] > x) ans[it->se] = it->fi;
                it++;
            }
        }
        
        now.clear();
        memset(tree, 0, sizeof tree);
    }
    
    forr(i, n)
    {
        if(ans[i] == Q) printf("NIE\n");
        else printf("%d\n", ans[i]+1);
    }
}
int main()
{
    //while(true)
        solve();
}

Compilation message

met.cpp: In function 'void solve()':
met.cpp:88:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |             auto [l, r] = q[i-1].fi;
      |                  ^
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:62:5: note: in expansion of macro 'getint'
   62 |     getint(n); getint(m);
      |     ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:62:16: note: in expansion of macro 'getint'
   62 |     getint(n); getint(m);
      |                ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:65:9: note: in expansion of macro 'getint'
   65 |         getint(a);
      |         ^~~~~~
met.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     forr(i, n) scanf("%d", p+i);
      |                ~~~~~^~~~~~~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:69:5: note: in expansion of macro 'getint'
   69 |     getint(Q);
      |     ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:9: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |         ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:20: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |                    ^~~~~~
met.cpp:6:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define getint(n) int n; scanf("%d%*c", &n)
      |                          ~~~~~^~~~~~~~~~~~~
met.cpp:72:31: note: in expansion of macro 'getint'
   72 |         getint(l); getint(r); getint(a);
      |                               ^~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9824 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Incorrect 7 ms 10024 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 11672 KB Output is correct
2 Correct 118 ms 13088 KB Output is correct
3 Incorrect 117 ms 12304 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 115 ms 12336 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 11892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 11780 KB Output is correct
2 Correct 130 ms 12240 KB Output is correct
3 Incorrect 83 ms 12228 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 794 ms 30904 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 790 ms 29292 KB Output isn't correct
2 Halted 0 ms 0 KB -