Submission #465212

# Submission time Handle Problem Language Result Execution time Memory
465212 2021-08-15T11:33:10 Z Vladth11 Bulldozer (JOI17_bulldozer) C++14
0 / 100
3 ms 588 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 debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 2001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;

int n;

class AINT{
public:
    struct Node{
        int st, dr, total;
        int ssm;
    };
    Node aint[NMAX * 4];
    Node combine(Node a, Node b){
        Node rez;
        rez.st = max(a.st, a.total + b.st);
        rez.dr = max(b.dr, b.total + a.dr);
        rez.total = a.total + b.total;
        rez.ssm = max({a.ssm, b.ssm, a.dr + b.st}); ///hmmm
        return rez;
    }
    void update(int node, int st, int dr, int a, int b){
        if(st == dr){
            aint[node] = {b, b, b, b};
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
    }
    Node best(){
        return aint[1];
    }
}st;

struct point{
    int x, y, val;
};

point v[NMAX], a[NMAX];
map <pii, int> mp;

struct event{
    pii p;
    double timp;
};

vector <event> events;

bool cmp(event a, event b){
    return a.timp < b.timp;
}

///De analizat
void swapElements(int a, int b){
    st.update(1, 1, n, mp[{v[a].x, v[a].y}], v[b].val);
    st.update(1, 1, n, mp[{v[b].x, v[b].y}], v[a].val);
    swap(mp[{v[b].x, v[b].y}], mp[{v[a].x, v[a].y}]);

}
///De analizat

bool cmpp(point a, point b){
    if(a.x != b.x)
        return a.x < b.x;
    return a.y > b.y;
}

void compute(int i, int j){
    events.push_back({{i, j}, (double)(v[i].y - v[j].y) / (double)(v[i].x - v[j].x)});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].x >> v[i].y >> v[i].val;
    }
    sort(v + 1, v + n + 1, cmpp);
    for(i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            compute(i, j);
        }
    }
    for(i = 1; i <= n; i++){
        st.update(1, 1, n, i, v[i].val);
        mp[{v[i].x, v[i].y}] = i;
    }
    sort(events.begin(), events.end(), cmp);
    int maxim = 0;
    for(i = 0; i < events.size(); i++){
        swapElements(events[i].p.first, events[i].p.second);
        if(i < events.size() - 1 && events[i].timp == events[i + 1].timp){
            continue;
        }
        maxim = max(maxim, st.best().ssm);
    }
    cout << maxim;
    return 0;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(i = 0; i < events.size(); i++){
      |                ~~^~~~~~~~~~~~~~~
bulldozer.cpp:117:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         if(i < events.size() - 1 && events[i].timp == events[i + 1].timp){
      |            ~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -