oj.uz

Submission #333514

# Submission time Handle Problem Language Result Execution time Memory
333514 2020-12-06T17:38:31 Z Vladth11 Meteors (POI11_met) C++14
74 / 100
 1630 ms 65540 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 300005;
const ll INF = (1 << 16) - 1;
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 35;
 
struct ura{
    ll a, b, c;
};
 
vector <ura> segm;
vector <ll> reg[NMAX];
vector <ll> check[NMAX];
ll n, m, k;
ll req[NMAX], l[NMAX], r[NMAX];
 
class AIB{
    ll aib[NMAX + 5];
    void update(ll x, ll val){
        for(ll i = x; i <= m; i+=i&(-i)){
            aib[i] += val;
        }
    }
    ll query(ll x){
        ll sum = 0;
        for(ll i = x; i > 0; i-=i&(-i)){
            sum += aib[i];
        }
        return sum;
    }
public:
    void ru(ll l, ll r, ll val){
        if(l <= r){
            update(l, val);
            update(r + 1, -val);
        }
        if(l > r){
            update(l, val);
            update(1, val);
            update(r + 1, -val);
        }
    }
    ll cn(ll x){
        return query(x);
    }
    void init(){
        for(ll i = 1; i <= m; i++){
            aib[i] = 0;
        }
    }
}aib;
 
void baga(){
    aib.init();
    ll i;
    for(i = 1; i <= k; i++)
        check[i].clear();
    for(i = 1; i <= n; i++){
      	if(l[i] == r[i])
          continue;
        ll mid = (l[i] + r[i]) / 2;
        check[mid].push_back(i);
    }
    for(i = 0; i < k; i++){
        aib.ru(segm[i].a, segm[i].b, segm[i].c);
        for(auto x : check[i + 1]){
            ll s = 0;
            for(auto y : reg[x]){
                s += aib.cn(y);
              if(s > 1e9)
                break;
            }
            ll mid = i + 1;
            if(s >= req[x]){
                r[x] = mid;
            }else{
                l[x] = mid + 1;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll i, x;
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        cin >> x;
        reg[x].push_back(i);
    }
    for(i = 1; i <= n; i++){
        cin >> req[i];
    }
    cin >> k;
    for(i = 1; i <= k; i++){
        ura x;
        cin >> x.a >> x.b >> x.c;
        segm.push_back(x);
    }
    for(i = 1; i <= n; i++){
        l[i] = 1;
        r[i] = k + 1;
    }
    for(ll i = 1; i <= nr_of_bits; i++){
        baga();
    }
    for(i = 1; i <= n; i++){
        if(l[i] != k + 1)
        cout << l[i] << "\n";
        else cout << "NIE\n";
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 12 ms 14572 KB Output is correct
3 Correct 12 ms 14572 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 12 ms 14572 KB Output is correct
3 Correct 12 ms 14572 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 17568 KB Output is correct
2 Correct 196 ms 20960 KB Output is correct
3 Correct 159 ms 19680 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 19044 KB Output is correct
2 Correct 169 ms 18960 KB Output is correct
3 Correct 204 ms 21088 KB Output is correct
4 Correct 47 ms 17968 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 18016 KB Output is correct
2 Correct 152 ms 21348 KB Output is correct
3 Correct 92 ms 16100 KB Output is correct
4 Correct 168 ms 20336 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 16608 KB Output is correct
2 Correct 175 ms 18880 KB Output is correct
3 Correct 130 ms 17120 KB Output is correct
4 Correct 197 ms 22496 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1600 ms 48064 KB Output is correct
2 Correct 1112 ms 29924 KB Output is correct
3 Correct 432 ms 22992 KB Output is correct
4 Runtime error 1344 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1630 ms 46048 KB Output is correct
2 Correct 1163 ms 30048 KB Output is correct
3 Correct 354 ms 23260 KB Output is correct
4 Runtime error 1276 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)